Fast FPT-approximation of branchwidth

DOI10.1137/22M153937XMaRDI QIDQ6593764zbMATH OpenFDO

Authors Fedor V. Fomin, Tuukka Korhonen

Publication date 27 August 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/22M153937X

zbMATH Keywords

approximation algorithmsbranchwidthcliquewidthgraph algorithmsparameterized algorithmsrankwidth

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(2)

• Space-efficient parameterized algorithms on graphs of low shrubdepth
• Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6593764)