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

**Harvard**

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

** BibTeX **

@article{

Damaschke2009,

author={Damaschke, Peter},

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

journal={Journal of Combinatorial Optimization (special issue COCOA 2008)},

issn={1382-6905},

volume={18},

issue={3},

pages={294-306},

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,
for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might
be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT
algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.},

year={2009},

keywords={hitting set, job assignment, parameterized algorithm, dynamic programming on subsets, cores in graphs},

}

** RefWorks **

RT Journal Article

SR Print

ID 101452

A1 Damaschke, Peter

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

YR 2009

JF Journal of Combinatorial Optimization (special issue COCOA 2008)

SN 1382-6905

VO 18

IS 3

SP 294

OP 306

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,
for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might
be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT
algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.

LA eng

DO 10.1007/s10878-009-9234-9

OL 30