Constructive algorithm for path-width of matroids

DOI10.1137/1.9781611974331.ch116zbMath1410.68377OpenAlexW3025751478MaRDI QIDQ4575700

Sang-il Oum, Eun Jung Kim, Jisu Jeong

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)

Related Items

Computing Tree Decompositions, A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth, Covering Vectors by Spaces: Regular Matroids, A Simpler Self-reduction Algorithm for Matroid Path-Width, Rank-width: algorithmic and structural results, Finding branch-decompositions of matroids, hypergraphs, and more, An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion, Edge-treewidth: algorithmic and combinatorial properties, On the optimality of pseudo-polynomial algorithms for integer programming, Unnamed Item, An FPT 2-approximation for tree-cut decomposition, 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, Unnamed Item, On the Optimality of Pseudo-polynomial Algorithms for Integer Programming, Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm, Finding Branch-Decompositions of Matroids, Hypergraphs, and More