Finding minimum height elimination trees for interval graphs in polynomial time

DOI10.1007/BF01934264zbMATH Open0822.68071OpenAlexW2070592419MaRDI QIDQ1347072FDOQ1347072

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

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

zbMATH Keywords

interval graphselimination treesparse matrix factorization

Mathematics Subject Classification ID

Combinatorics in computer science (68R05)

Cites Work

• Title not available (Why is that?)
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Incidence matrices and interval graphs
• On rigid circuit graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Characterization of Comparability Graphs and of Interval 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
• Computing the Minimum Fill-In is NP-Complete
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting clique trees and computing perfect elimination schemes in parallel
• Power of Natural Semijoins
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (13)

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

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)