Fast Gaussian elimination for low treewidth matrices

DOI10.4230/LIPICS.ESA.2025.116MaRDI QIDQ7322534zbMATH OpenFDO

Authors Martin Fürer, Carlos Hoppen, Vilmar Trevisan

Publication date 31 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ESA.2025.116

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• A c^k n 5-approximation algorithm for treewidth
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A nearly-linear time algorithm for linear programs with small treewidth: a multiscale representation of robust central path
• Algorithmic Aspects of Vertex Elimination on Directed Graphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Efficient algorithms for solving systems of linear equations and path problems
• Efficient diagonalization of symmetric matrices associated with graphs of small treewidth
• Fully polynomial-time parameterized computations for graphs and matrices of low treewidth
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Nonserial dynamic programming
• On tree-partition-width
• Perfect Elimination and Chordal Bipartite Graphs
• S-functions for graphs
• The Use of Linear Graphs in Gauss Elimination
• Treewidth. Computations and approximations
• Triangulated graphs and the elimination process

This page was built for publication: Fast Gaussian elimination for low treewidth matrices

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