Minimizing elimination tree height can increase fill more than linearly

DOI10.1016/0020-0190(95)90815-IMaRDI QIDQ671941zbMATH OpenOpenAlexFDO

Authors Bengt Aspvall

Publication date 27 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(95)90815-i

zbMATH Keywords

Parallel processingChordal completionElimination treeFillSparse matrixVertex elimination

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10) Linear equations (linear algebraic aspects) (15A06)

Recommendations

• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• A practical algorithm for making filled graphs minimal
• Finding minimum height elimination trees for interval graphs in polynomial time
• Making an arbitrary filled graph minimal by removing fill edges
• The General Minimum Fill-In Problem

Cites work

• scientific article; zbMATH DE number 554763 (Why is no real title available?)
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Parallel Algorithms for Sparse Linear Systems
• The Role of Elimination Trees in Sparse Factorization

Cited in

(2)

• Constructing a minimum height elimination tree of a tree in linear time
• Finding minimum height elimination trees for interval graphs in polynomial time

This page was built for publication: Minimizing elimination tree height can increase fill more than linearly

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