Τίτλος:
The parameterized complexity of graph cyclability
Γλώσσες Τεκμηρίου:
Αγγλικά
Περίληψη:
The cyclability of a graph is the maximum integer k for which every k vertices lie on a cycle. The algorithmic version of the problem, given a graph G and a non-negative integer k, decide whether the cyclability of G is at least k, is NP-hard. We prove that this problem, parameterized by k, is co-W[1]-hard. We give an FPT algorithm for planar graphs that runs in time 2 2O(k2 log k) · n2. Our algorithm is based on a series of graph theoretical results on cyclic linkages in planar graphs. © 2014 Springer-Verlag Berlin Heidelberg.
Συγγραφείς:
Golovach, P.A.
Kamiński, M.
Maniatis, S.
Thilikos, D.M.
Περιοδικό:
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Λέξεις-κλειδιά:
Algorithms; Graphic methods; Polynomials, Cyclability; FPT algorithms; Graph G; Nonnegative integers; NP-hard; Parameterized; Parameterized complexity; Planar graph, Graph theory
DOI:
10.1007/978-3-662-44777-2_41
