Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
From MaRDI portal
Publication:547307
DOI10.1007/s00453-010-9390-4zbMath1219.68123OpenAlexW2005515778MaRDI 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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items (2)
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 3 ) Time
- (Meta) Kernelization
- Mathematical Foundations of Computer Science 2004
- Dynamic Programming and Fast Matrix Multiplication
- Algorithms – ESA 2005
This page was built for publication: Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
