Vertex rankings of chordal graphs and weighted trees

DOI10.1016/J.IPL.2005.12.006MaRDI QIDQ844166zbMATH OpenOpenAlexWikidataFDO

Authors Dariusz Dereniowski, Adam Nadolski

Publication date 18 January 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2005.12.006

zbMATH Keywords

computational complexitygraph algorithmsvertex rankingchordal graph

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Nonnumerical algorithms (68W05)

Recommendations

• Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
• Edge ranking of weighted trees
• Algorithms for generalized vertex-rankings of partial k-trees
• Rankings of Graphs
• Optimal vertex ranking of block graphs

Cites work

• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Edge ranking of weighted trees
• Finding minimum height elimination trees for interval graphs in polynomial time
• Incidence matrices and interval graphs
• On rigid circuit graphs
• On the vertex ranking problem for trapezoid, circular-arc and other graphs
• Rankings of Graphs
• The Role of Elimination Trees in Sparse Factorization

Cited in

(14)

• On vertex rankings of graphs and its relatives
• On the size of minimal separators for treedepth decomposition
• scientific article; zbMATH DE number 1088275 (Why is no real title available?)
• Minimum vertex ranking spanning tree problem for chordal and proper interval graphs
• Constructing a minimum height elimination tree of a tree in linear time
• Optimal vertex ranking of block graphs
• Rank inequalities for chordal graphs
• Minimal \(k\)-rankings and the rank number of \(P^2_n\)
• NP-hardness proof and an approximation algorithm for the minimum vertex ranking spanning tree problem
• Rank numbers of grid graphs
• The complexity of bicriteria tree-depth
• The complexity of bicriteria tree-depth
• Graphs with large rank numbers and rank numbers of subdivided stars
• Vertex ranking with capacity

This page was built for publication: Vertex rankings of chordal graphs and weighted trees

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