Finding Branch-Decompositions of Matroids, Hypergraphs, and More

DOI10.1137/19M1285895zbMath1499.68278OpenAlexW3212225902MaRDI QIDQ5013567

Sang-il Oum, Jisu Jeong, Eun Jung Kim

Publication date: 1 December 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/19m1285895

zbMATH Keywords

matroidfixed-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 (2)

Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Edge-treewidth: algorithmic and combinatorial properties

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Testing branch-width
• Graph minors. X: Obstructions to tree-decomposition
• Call routing and the ratcatcher
• On the excluded minors for the matroids of branch-width \(k\)
• Upper bounds to the clique width of graphs
• The rank-width of edge-coloured graphs
• Branch-width, parse trees, and monadic second-order logic for matroids.
• Approximating clique-width and branch-width
• Clique-Width is NP-Complete
• 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
• On Integer Programming and the Branch-Width of the Constraint Matrix
• Finding Branch-Decompositions and Rank-Decompositions

This page was built for publication: Finding Branch-Decompositions of Matroids, Hypergraphs, and More