Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
type: Item
instance of: scholarly article
title: Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
zbMATH Open document ID: 1219.68123
author: Athanassios Koutsonas
author: Dimitrios M. Thilikos
published in: Algorithmica
publication date: 2011-07-01T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5916753
zbMATH Keywords: branchwidth
zbMATH Keywords: parameterized algorithms
zbMATH Keywords: feedback vertex set
zbMATH Keywords: face cover
MaRDI profile type: Publication
full work available at URL: s00453-010-9390-4
OpenAlex ID: W2005515778
cites work: Q4488089
cites work: A Cubic Kernel for Feedback Vertex Set
cites work: A Linear Kernel for Planar Feedback Vertex Set
cites work: A Linear Kernel for the k-Disjoint Cycle Problem on Planar Graphs
cites work: (Meta) Kernelization
cites work: Improved algorithms for feedback vertex set problems
cites work: A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
cites work: Exponential speedup of fixed-parameter algorithms for classes of graphs excluding single-crossing graphs as minors
cites work: Dynamic Programming and Fast Matrix Multiplication
cites work: Algorithms – ESA 2005
cites work: Q3579494
cites work: Subexponential parameterized algorithms
cites work: Mathematical Foundations of Computer Science 2004
cites work: Q3145802
cites work: Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
cites work: New upper bounds on the decomposability of planar graphs
cites work: On the minimum feedback vertex set problem: Exact and enumeration algorithms
cites work: Primal-dual approximation algorithms for feedback problems in planar graphs
cites work: Optimal branch-decomposition of planar graphs in O ( n 3 ) Time
cites work: Planar branch decompositions. I: The ratcatcher
cites work: Planar branch decompositions. II: The cycle method
cites work: Q4414505
cites work: Q5710169
cites work: Graph minors. X: Obstructions to tree-decomposition
cites work: Call routing and the ratcatcher
DOI: 10.1007/S00453-010-9390-4
description: scientific article; zbMATH DE number 5916753