Constructive linear time algorithms for branchwidth

DOI10.1007/3-540-63165-8_217zbMath1401.05277OpenAlexW1551429295MaRDI QIDQ4571992

Dimitrios M. Thilikos, Hans L. Bodlaender

Publication date: 4 July 2018

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/18903

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Computing Tree Decompositions ⋮ (Total) vector domination for graphs with bounded branchwidth ⋮ FPT algorithms to enumerate and count acyclic and totally cyclic orientations ⋮ An analysis of the parameterized complexity of periodic timetabling ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ Subexponential Fixed-Parameter Algorithms for Partial Vector Domination ⋮ Testing branch-width ⋮ Finding branch-decompositions of matroids, hypergraphs, and more ⋮ Edge-treewidth: algorithmic and combinatorial properties ⋮ Tangle bases: Revisited ⋮ Practical algorithms for branch-decompositions of planar graphs ⋮ Unnamed Item ⋮ Typical sequences revisited -- computing width parameters of graphs ⋮ Square roots of minor closed graph classes ⋮ An Upper Bound for Resolution Size: Characterization of Tractable SAT Instances ⋮ Subexponential parameterized algorithms ⋮ Confronting intractability via parameters ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Subexponential fixed-parameter algorithms for partial vector domination ⋮ Branchwidth of chordal graphs ⋮ Computing the branchwidth of interval graphs ⋮ Unnamed Item ⋮ Graphs, branchwidth, and tangles! Oh my! ⋮ Branch-width, parse trees, and monadic second-order logic for matroids. ⋮ Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time ⋮ Unnamed Item ⋮ A Local Search Algorithm for Branchwidth ⋮ Branch decompositions and minor containment ⋮ Derivation of algorithms for cutwidth and related graph layout parameters ⋮ Finding Branch-Decompositions of Matroids, Hypergraphs, and More

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forbidden minors characterization of partial 3-trees
• Characterization of partial 3-trees in terms of three structures
• Graph minors. X: Obstructions to tree-decomposition
• On the complexity of finding iso- and other morphisms for partial \(k\)- trees
• Call routing and the ratcatcher
• Algorithms finding tree-decompositions of graphs
• Steiner trees, partial 2–trees, and minimum IFI networks
• A characterization of partial 3-trees
• Characterization and Recognition of Partial 3-Trees
• Complexity of Finding Embeddings in a k-Tree
• Parallel Algorithms with Optimal Speedup for Bounded Treewidth
• An algebraic theory of graph reduction
• Treewidth and Pathwidth of Permutation Graphs
• On Linear Recognition of Tree-Width at Most Four
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth