Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms

DOI10.1007/978-3-540-92248-3_24zbMath1202.68284OpenAlexW1584291908MaRDI QIDQ5302061

Athanassios Koutsonas, Dimitrios M. Thilikos

Publication date: 20 January 2009

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_24

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (1)

Connecting face hitting sets in planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential parameterized algorithms
• 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
• Parametrized complexity theory.
• New upper bounds on the decomposability of planar graphs
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• A Cubic Kernel for Feedback Vertex Set
• Improved Algorithms for the Feedback Vertex Set Problems
• Mathematical Foundations of Computer Science 2004
• Dynamic Programming and Fast Matrix Multiplication
• Automata, Languages and Programming

This page was built for publication: Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms