Fast Computation of Minimal Fill Inside A Given Elimination Ordering

DOI10.1137/070680680MaRDI QIDQ3642841zbMATH OpenOpenAlexFDO

Authors Pinar Heggernes, Barry W. Peyton

Publication date 6 November 2009

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

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

zbMATH Keywords

composite tree rotationselimination treesmaximum cardinality search (MCS)minimal fillminimal triangulationsparse matrix computations

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Applications of graph theory (05C90) Direct numerical methods for linear systems and matrix inversion (65F05) Computational methods for sparse matrices (65F50)

Recommendations

• Faster Parameterized Algorithms for Minimum Fill-In
• Faster parameterized algorithms for \textsc{Minimum Fill-in}
• scientific article; zbMATH DE number 554763
• A practical algorithm for making filled graphs minimal
• A Polynomial Approximation Algorithm for the Minimum Fill-In Problem
• scientific article; zbMATH DE number 1775386
• Subexponential parameterized algorithm for minimum fill-in
• scientific article; zbMATH DE number 7053390
• Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds

Cited in

(15)

• Finding minimum height elimination trees for interval graphs in polynomial time
• A practical algorithm for making filled graphs minimal
• Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
• Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
• scientific article; zbMATH DE number 3844934 (Why is no real title available?)
• On the Performance of the Minimum Degree Ordering for Gaussian Elimination
• scientific article; zbMATH DE number 5556488 (Why is no real title available?)
• The General Minimum Fill-In Problem
• scientific article; zbMATH DE number 554763 (Why is no real title available?)
• Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
• Minimal elimination of planar graphs
• A survey of direct methods for sparse linear systems
• Minimal elimination ordering for graphs of bounded degree
• Minimizing elimination tree height can increase fill more than linearly
• Minimal fill in O(\(n^{2.69}\)) time

This page was built for publication: Fast Computation of Minimal Fill Inside A Given Elimination Ordering

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