Constructing a minimum height elimination tree of a tree in linear time

DOI10.1016/J.INS.2007.02.002MaRDI QIDQ881880zbMATH OpenOpenAlexFDO

Authors Chung-Hsien Hsu, Sheng-Lung Peng, Chong-Hui Shi

Publication date 18 May 2007

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ins.2007.02.002

zbMATH Keywords

elimination treesgraph algorithmstreesvertex ranking

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 975346
• Finding minimum height elimination trees for interval graphs in polynomial time
• On Polynomial Time Constructions of Minimum Height Decision Tree
• On constructing the elimination tree
• scientific article; zbMATH DE number 219228
• Construction of a tree from its traversals in optimal time and space
• Minimax trees in linear time with applications
• Minimax Trees in Linear Time with Applications
• scientific article; zbMATH DE number 4198042
• Linear-time construction of treaps and Cartesian trees

Cites work

• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Biconvex graphs: Ordering and algorithms
• Efficient algorithms for graphs with few P₄'s
• Finding minimum height elimination trees for interval graphs in polynomial time
• Minimizing elimination tree height can increase fill more than linearly
• On a graph partition problem with application to VLSI layout
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• On vertex ranking of a starlike graph
• Optimal edge ranking of trees in linear time
• Optimal node ranking of tree in linear time
• Optimal node ranking of trees
• Ordered colourings
• Rankings of Graphs
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The Role of Elimination Trees in Sparse Factorization
• Vertex ranking of asteroidal triple-free graphs
• Vertex rankings of chordal graphs and weighted trees

Cited in

(1)

• On constructing the elimination tree

This page was built for publication: Constructing a minimum height elimination tree of a tree in linear time

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