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

minimal triangulationminimal fillelimination treessparse matrix computationscomposite tree rotationsmaximum cardinality search (MCS)

Mathematics Subject Classification ID

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

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)

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

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)