Fast FPT-approximation of branchwidth

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

Unnamed Item
Finding odd cycle transversals.
Boolean-width of graphs
Vertex-minors, monadic second-order logic, and a conjecture by Seese
Testing branch-width
MSOL partitioning problems on graphs of bounded treewidth and clique-width
$H$-join decomposable graphs and algorithms with runtime single exponential in rankwidth
On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Graph minors. X: Obstructions to tree-decomposition
Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
Call routing and the ratcatcher
$k$-NLC graphs and polynomial algorithms
Edge dominating set and colorings on graphs with fixed clique-width
Algorithms for vertex-partitioning problems on graphs with fixed clique-width.
Linear time solvable optimization problems on graphs of bounded clique-width
Handle-rewriting hypergraph grammars
On powers of graphs of bounded NLC-width (clique-width)
Rank-width: algorithmic and structural results
Branch-width, parse trees, and monadic second-order logic for matroids.
Approximating clique-width and branch-width
Rank-width and vertex-minors
The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
A $c^k n$ 5-Approximation Algorithm for Treewidth
Tour Merging via Branch-Decomposition
Easy problems for tree-decomposable graphs
Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
Clique-Width is NP-Complete
Handbook of Graph Grammars and Computing by Graph Transformation
Constructive linear time algorithms for branchwidth
A Branch Decomposition Algorithm for the p-Median Problem
Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Approximating rank-width and clique-width quickly
Finding Branch-Decompositions of Matroids, Hypergraphs, and More
Evaluations of Graph Polynomials
A Parametrized Algorithm for Matroid Branch-Width
Parameterized Algorithms
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
Finding Branch-Decompositions and Rank-Decompositions
On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs

This page was built for publication: Fast FPT-approximation of branchwidth