EUVIMEDObjevte EUVIMED
Crossref

Improving Vertex Cover as a Graph Parameter

Robert Ganian

Discrete Mathematics & Theoretical Computer Science · 2015-09-14 · Vol. 17 no.2 (Discrete Algorithms)

DOI: 10.46298/dmtcs.2136 ↗

At a glance

Journal article in Discrete Mathematics & Theoretical Computer Science, published online on 2015-09-14. Written by Robert Ganian. Cited 14 times so far (Crossref). Funded by: Austrian Science Fund.

AbstraktBibliografické údajeCiteRelated studies

Abstract (original language)

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.

Funding

  • Austrian Science Fund

Cite

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}
}
Start for free →