Finding minimum height elimination trees for interval graphs in polynomial time

DOI10.1007/BF01934264MaRDI QIDQ1347072zbMATH OpenOpenAlexFDO

Authors Bengt Aspvall, Pinar Heggernes

Publication date 19 June 1995

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01934264

zbMATH Keywords

elimination treeinterval graphssparse matrix factorization

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Recommendations

• Fast Computation of Minimal Fill Inside A Given Elimination Ordering
• On constructing the elimination tree
• Efficient Parallel Algorithms for Chordal Graphs
• Minimizing elimination tree height can increase fill more than linearly
• Fast Parallel Algorithms for Chordal Graphs

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Computing the Minimum Fill-In is NP-Complete
• Counting clique trees and computing perfect elimination schemes in parallel
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3520320 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 751126 (Why is no real title available?)
• scientific article; zbMATH DE number 1414315 (Why is no real title available?)
• scientific article; zbMATH DE number 3307459 (Why is no real title available?)
• scientific article; zbMATH DE number 3383914 (Why is no real title available?)
• Incidence matrices and interval graphs
• On rigid circuit graphs
• Power of Natural Semijoins
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The Role of Elimination Trees in Sparse Factorization

Cited in

(15)

• Finding the edge ranking number through vertex partitions
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• On the diameter of tree associahedra
• A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs
• Compact representation of graphs with bounded bandwidth or treedepth
• A heuristic approach to the treedepth decomposition problem for large graphs
• Vertex ranking of asteroidal triple-free graphs
• Competitive Online Search Trees on Trees
• Vertex ranking of asteroidal triple-free graphs
• Minimizing elimination tree height can increase fill more than linearly
• Optimal blocks for maximizing the transaction fee revenue of bitcoin miners
• Combinatorial generation via permutation languages. IV: Elimination trees
• Vertex rankings of chordal graphs and weighted trees
• Constructing a minimum height elimination tree of a tree in linear time
• Optimal vertex ranking of block graphs

This page was built for publication: Finding minimum height elimination trees for interval graphs in polynomial time

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