Finding branch-decompositions of matroids, hypergraphs, and more

DOI10.4230/LIPIcs.ICALP.2018.80zbMath1499.68277arXiv1711.01381OpenAlexW2963663205MaRDI QIDQ5002759

Eun Jung Kim, Sang-il Oum, Jisu Jeong

Publication date: 28 July 2021

Full work available at URL: https://arxiv.org/abs/1711.01381

zbMATH Keywords

fixed-parameter tractabilityrank-widthbranch-widthcarving-width

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of matroids and geometric lattices (05B35) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (7)

Computing Tree Decompositions ⋮ A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Branch-depth: generalizing tree-depth of graphs ⋮ The grid theorem for vertex-minors ⋮ Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm for Integer Programming

Cites Work

• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• On the excluded minors for the matroids of branch-width \(k\)
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Approximating clique-width and branch-width
• The “Art of Trellis Decoding” Is Fixed-Parameter Tractable
• Constructive linear time algorithms for branchwidth
• Constructive algorithm for path-width of matroids
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• A Parametrized Algorithm for Matroid Branch-Width
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Finding branch-decompositions of matroids, hypergraphs, and more