Côd QR

The Parameterized Complexity of the Rainbow Subgraph Problem

The NP-hard RAINBOW SUBGRAPH problem, motivated from bioinformatics, is to find in an edge-colored graph a subgraph that contains each edge color exactly once and has at most \(k\) vertices. We examine the parameterized complexity of RAINBOW SUBGRAPH for paths, trees, and general graphs. We sho...

Disgrifiad llawn

Wedi'i Gadw mewn:
Prif Awduron: Falk Hüffner, Christian Komusiewicz, Rolf Niedermeier, Martin Rötzschke
Fformat: Artigo
Iaith:Inglês
Cyhoeddwyd: MDPI AG 2015-02-01
Cyfres:Algorithms
Pynciau:
APX-hardness
multivariate complexity analysis
fixed-parameter tractability
parameterized hardness
problem kernel
haplotyping
Mynediad Ar-lein:http://www.mdpi.com/1999-4893/8/1/60
Tagiau: Ychwanegu Tag
Dim Tagiau, Byddwch y cyntaf i dagio'r cofnod hwn!

Eitemau Tebyg