The Parameterized Complexity of Graph Cyclability

DOI10.1007/978-3-662-44777-2_41zbMath1425.05033arXiv1412.3955OpenAlexW2963337508MaRDI QIDQ5891809

Petr A. Golovach, Marcin Kaminski, Dimitrios M. Thilikos, Spyridon Maniatis

Publication date: 8 October 2014

Published in: SIAM Journal on Discrete Mathematics, Algorithms - ESA 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.3955

zbMATH Keywords

treewidthlinkagescyclabilityparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Cyclability in graph classes, Combing a Linkage in an Annulus, Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm, Unnamed Item, Modification to Planarity is Fixed Parameter Tractable, Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Graph minors. XXII. Irrelevant vertices in linkage problems
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• A generalization of Dirac's theorem on cycles through \(k\) vertices in \(k\)-connected graphs
• Graph minors. XXI. graphs with unique linkages
• Graph minors. X: Obstructions to tree-decomposition
• Embedding grids in surfaces
• Graph minors. XIII: The disjoint paths problem
• Cycles through 23 vertices in 3-connected cubic planar graphs
• Contraction obstructions for treewidth
• Parametrized complexity theory.
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• A shorter proof of the graph minor algorithm
• Tight Bounds for Linkages in Planar Graphs
• Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
• In abstrakten Graphen vorhandene vollständige 4‐Graphen und ihre Unterteilungen
• The Bidimensional Theory of Bounded-Genus Graphs
• Fast Minor Testing in Planar Graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• A nine vertex theorem for 3-connected claw- free graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Kernelization Lower Bounds by Cross-Composition
• (Meta) Kernelization
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• Parameterized Algorithms
• Cycles and Connectivity in Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth