Finding minimum height elimination trees for interval graphs in polynomial time
From MaRDI portal
Publication:1347072
DOI10.1007/BF01934264zbMath0822.68071OpenAlexW2070592419MaRDI QIDQ1347072
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
Related Items (11)
Vertex ranking of asteroidal triple-free graphs ⋮ Vertex rankings of chordal graphs and weighted trees ⋮ A polynomial time algorithm for obtaining minimum edge ranking on two-connected outerplanar graphs ⋮ Constructing a minimum height elimination tree of a tree in linear time ⋮ Compact representation of graphs with bounded bandwidth or treedepth ⋮ A heuristic approach to the treedepth decomposition problem for large 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 ⋮ Optimal vertex ranking of block graphs ⋮ Competitive Online Search Trees on Trees
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
This page was built for publication: Finding minimum height elimination trees for interval graphs in polynomial time
