Constructive algorithm for path-width of matroids

DOI10.1137/1.9781611974331.CH116MaRDI QIDQ4575700zbMATH OpenOpenAlexFDO

Authors Jisu Jeong, Eun Jung Kim, Sang-Il Oum

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611974331.ch116

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• A simpler self-reduction algorithm for matroid path-width
• Finding branch-decompositions of matroids, hypergraphs, and more
• Finding branch-decompositions of matroids, hypergraphs, and more
• Matroid Pathwidth and Code Trellis Complexity
• Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)

Cited in

(20)

• On the optimality of pseudo-polynomial algorithms for integer programming
• On the optimality of pseudo-polynomial algorithms for integer programming
• Obstructions for matroids of path-width at most \(k\) and graphs of linear rank-width at most \(k\)
• Graph theory. Abstracts from the workshop held January 2--8, 2022
• On the parameterized complexity of \textsc{Girth} and \textsc{Connectivity} problems on linear matroids
• A simpler self-reduction algorithm for matroid path-width
• A linear fixed parameter tractable algorithm for connected pathwidth
• Computing Tree Decompositions
• Edge-treewidth: algorithmic and combinatorial properties
• scientific article; zbMATH DE number 7651203 (Why is no real title available?)
• Finding branch-decompositions of matroids, hypergraphs, and more
• Finding branch-decompositions of matroids, hypergraphs, and more
• An augmenting path algorithm for linear matroid parity
• Rank-width: algorithmic and structural results
• Matroid Pathwidth and Code Trellis Complexity
• Covering Vectors by Spaces: Regular Matroids
• An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion
• Computing paths of large rank in planar frameworks deterministically
• scientific article; zbMATH DE number 7471715 (Why is no real title available?)
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm

This page was built for publication: Constructive algorithm for path-width of matroids

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