Minimizing elimination tree height can increase fill more than linearly

DOI10.1016/0020-0190(95)90815-IzbMATH Open0875.68695OpenAlexW2031013415MaRDI QIDQ671941FDOQ671941

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

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

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)

Cites Work

• The Role of Elimination Trees in Sparse Factorization
• Parallel Algorithms for Sparse Linear Systems
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Title not available (Why is that?)

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)