Algorithms | |
The Parameterized Complexity of the Rainbow Subgraph Problem |
|
Falk Hﳿner2  Christian Komusiewicz1  Rolf Niedermeier2  Martin Rötzschke2  | |
[1] Institut für Softwaretechnik und Theoretische Informatik, TU Berlin, Ernst-Reuter-Platz 7, D-10587 Berlin, |
|
关键词: APX-hardness; multivariate complexity analysis; fixed-parameter tractability; parameterized hardness; problem kernel; haplotyping; | |
DOI : 10.3390/a8010060 | |
来源: mdpi | |
【 摘 要 】
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
【 授权许可】
CC BY
© 2015 by the authors; licensee MDPI, Basel, Switzerland
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
RO202003190015768ZK.pdf | 292KB | download |