Finding minimum height elimination trees for interval graphs in polynomial time

DOI10.1007/BF01934264zbMath0822.68071MaRDI QIDQ1347072

Bengt Aspvall, Pinar Heggernes

Publication date: 19 June 1995

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

sparse matrix factorization; interval graphs; elimination tree

Mathematics Subject Classification ID

68R05: Combinatorics in computer science

Related Items

Vertex ranking of asteroidal triple-free graphs, 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, 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

Cites Work

• On rigid circuit graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Counting clique trees and computing perfect elimination schemes in parallel
• Incidence matrices and interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• The Role of Elimination Trees in Sparse Factorization
• Power of Natural Semijoins
• Computing the Minimum Fill-In is NP-Complete
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item