Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms

DOI10.1007/s00453-010-9390-4zbMath1219.68123MaRDI QIDQ547307

Athanassios Koutsonas, Dimitrios M. Thilikos

Publication date: 1 July 2011

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-010-9390-4

zbMATH Keywords

feedback vertex set; parameterized algorithms; branchwidth; face cover

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

Related Items

Unnamed Item, Fixed-Parameter Tractability of Treewidth and Pathwidth

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential parameterized algorithms
• Improved algorithms for feedback vertex set problems
• On the minimum feedback vertex set problem: Exact and enumeration algorithms
• Graph minors. X: Obstructions to tree-decomposition
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Primal-dual approximation algorithms for feedback problems in planar graphs
• Call routing and the ratcatcher
• Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
• Planar Branch Decompositions I: The Ratcatcher
• Planar Branch Decompositions II: The Cycle Method
• New upper bounds on the decomposability of planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• A Linear Kernel for Planar Feedback Vertex Set
• A Cubic Kernel for Feedback Vertex Set
• A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
• Optimal branch-decomposition of planar graphs in O ( n ³ ) Time
• (Meta) Kernelization
• Mathematical Foundations of Computer Science 2004
• Dynamic Programming and Fast Matrix Multiplication
• Algorithms – ESA 2005