EUVIMEDEUVIMED entdecken
Crossref

A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems

Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier

ACM Transactions on Computation Theory · 2011

DOI: 10.1145/1944857.1944860 ↗

Kurz gefasst

Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2011. Verfasst von Michael R. Fellows und 3 weiteren Autor:innen. Die Arbeit wurde bisher 8-mal zitiert (Crossref) und nennt 24 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We investigate the computational complexity of a general “compression task” centrally occurring in the recently developed technique of iterative compression for exactly solving NP-hard minimization problems. The core issue (particularly but not only motivated by iterative compression) is to determine the computational complexity of the following task: given an already inclusion-minimal solution for an underlying (typically NP-hard) vertex deletion problem in graphs, find a smaller disjoint solution. The complexity of this task is so far lacking a systematic study. We consider a large class of vertex deletion problems on undirected graphs and show that a few cases are polynomial-time solvable, and the others are NP-hard. The considered class of vertex deletion problems includes Vertex Cover (where the compression task is polynomial time) and Undirected Feedback Vertex Set (where the compression task is NP-complete).

Zitieren

APA

Fellows, M. R., Guo, J., Moser, H., & Niedermeier, R. (2011). A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. ACM Transactions on Computation Theory. https://doi.org/10.1145/1944857.1944860

Vancouver

Fellows MR, Guo J, Moser H, Niedermeier R. A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems. ACM Transactions on Computation Theory. 2011. doi:10.1145/1944857.1944860

BibTeX
@article{Fellows2011,
  author = {Fellows, Michael R. and Guo, Jiong and Moser, Hannes and Niedermeier, Rolf},
  title = {A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems},
  journal = {ACM Transactions on Computation Theory},
  year = {2011},
  doi = {10.1145/1944857.1944860}
}
Kostenlos starten →