Presents the first single-exponential algorithm for hypergraph branchwidth at O*(4^n) and an improved O(3.293^n) algorithm for graphs that also outperforms prior practical implementations.
Branch-width of connectivity functions is fixed-parameter tractable
3 Pith papers cite this work. Polarity classification is still indexing.
3
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
years
2026 3roles
background 1polarities
background 1representative citing papers
O(n² + n^ω)-time algorithm decides if branch-width of a matrix-represented matroid over a finite field is at most k.
A unified framework yields eight depth measures on matroids with six shown functionally inequivalent, two matching branch-depth and tree-depth, and all coinciding on matroids versus matrices over any field.
citing papers explorer
-
Fast and Practical Single-Exponential Algorithms for Branchwidth
Presents the first single-exponential algorithm for hypergraph branchwidth at O*(4^n) and an improved O(3.293^n) algorithm for graphs that also outperforms prior practical implementations.
-
Branch-width of represented matroids in matrix multiplication time
O(n² + n^ω)-time algorithm decides if branch-width of a matrix-represented matroid over a finite field is at most k.
-
Measuring Depth of Matroids
A unified framework yields eight depth measures on matroids with six shown functionally inequivalent, two matching branch-depth and tree-depth, and all coinciding on matroids versus matrices over any field.