Improving Vertex Cover as a Graph Parameter
Discrete Mathematics & Theoretical Computer Science · 14.09.2015 · Vol. 17 no.2 (Discrete Algorithms)
DOI: 10.46298/dmtcs.2136 ↗Kurz gefasst
Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 14.09.2015. Verfasst von Robert Ganian. Die Arbeit wurde bisher 14-mal zitiert (Crossref). Gefördert von: Austrian Science Fund.
Abstract (Originalsprache)
Parameterized algorithms are often used to efficiently solve NP-hard problems on graphs. In this context, vertex cover is used as a powerful parameter for dealing with graph problems which are hard to solve even when parameterized by tree-width; however, the drawback of vertex cover is that bounding it severely restricts admissible graph classes. We introduce a generalization of vertex cover called twin-cover and show that FPT algorithms exist for a wide range of difficult problems when parameterized by twin-cover. The advantage of twin-cover over vertex cover is that it imposes a lesser restriction on the graph structure and attains low values even on dense graphs. Apart from introducing the parameter itself, this article provides a number of new FPT algorithms parameterized by twin-cover with a special emphasis on solving problems which are not in FPT even when parameterized by tree-width. It also shows that MS1 model checking can be done in elementary FPT time parameterized by twin-cover and discusses the field of kernelization.
Förderung
- Austrian Science Fund
Zitieren
APA
Ganian, R. (2015). Improving Vertex Cover as a Graph Parameter. Discrete Mathematics & Theoretical Computer Science, Vol. 17 no.2(Discrete Algorithms). https://doi.org/10.46298/dmtcs.2136
Vancouver
Ganian R. Improving Vertex Cover as a Graph Parameter. Discrete Mathematics & Theoretical Computer Science. 2015;Vol. 17 no.2(Discrete Algorithms). doi:10.46298/dmtcs.2136
BibTeX
@article{Ganian2015,
author = {Ganian, Robert},
title = {Improving Vertex Cover as a Graph Parameter},
journal = {Discrete Mathematics & Theoretical Computer Science},
year = {2015},
volume = {Vol. 17 no.2},
number = {Discrete Algorithms},
doi = {10.46298/dmtcs.2136}
}
EUVIMED