### Skapa referens, olika format (klipp och klistra)

**Harvard**

Damaschke, P. (2008) *Multiple hypernode hitting sets and smallest two-cores with targets*.

** BibTeX **

@conference{

Damaschke2008,

author={Damaschke, Peter},

title={Multiple hypernode hitting sets and smallest two-cores with targets},

booktitle={2nd International Conference on Combinatorial Optimization and Applications COCOA 2008, Lecture Notes in Computer Science},

isbn={978-3-540-85096-0},

pages={32-42},

abstract={The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that it remains fixed-parameter tractable (FPT) for m=2, with the number of hyperedges as the parameter. This is accomplished by a nontrivial extension of the known dynamic programming algorithm for usual hypergraphs. The result might be of independent interest for assignment problems, but here we need it as an auxiliary result to solve a different problem motivated by network analysis: We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices in a graph, with the number of targets as the parameter. (A d-core is a subgraph where every vertex has degree at least d within the subgraph.) This FPT result is best possible, in the sense that an FPT algorithm for 3-cores cannot exist, for simple reasons.},

year={2008},

keywords={hitting set, fixed-parameter tractability, dynamic programming, cores in graphs},

}

** RefWorks **

RT Conference Proceedings

SR Print

ID 73482

A1 Damaschke, Peter

T1 Multiple hypernode hitting sets and smallest two-cores with targets

YR 2008

T2 2nd International Conference on Combinatorial Optimization and Applications COCOA 2008, Lecture Notes in Computer Science

SN 978-3-540-85096-0

SP 32

OP 42

AB The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that it remains fixed-parameter tractable (FPT) for m=2, with the number of hyperedges as the parameter. This is accomplished by a nontrivial extension of the known dynamic programming algorithm for usual hypergraphs. The result might be of independent interest for assignment problems, but here we need it as an auxiliary result to solve a different problem motivated by network analysis: We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices in a graph, with the number of targets as the parameter. (A d-core is a subgraph where every vertex has degree at least d within the subgraph.) This FPT result is best possible, in the sense that an FPT algorithm for 3-cores cannot exist, for simple reasons.

LA eng

OL 30