EUVIMEDEUVIMED entdecken
Crossref

Improving Vertex Cover as a Graph Parameter

Robert Ganian

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →