Vertex rankings of chordal graphs and weighted trees
From MaRDI portal
Publication:844166
DOI10.1016/j.ipl.2005.12.006zbMath1187.68340OpenAlexW2009372021WikidataQ56767305 ScholiaQ56767305MaRDI QIDQ844166
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
Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
Constructing a minimum height elimination tree of a tree in linear time ⋮ Graphs with large rank numbers and rank numbers of subdivided stars ⋮ Optimal vertex ranking of block graphs ⋮ Minimal \(k\)-rankings and the rank number of \(P^2_n\) ⋮ Rank numbers of grid graphs ⋮ The complexity of bicriteria tree-depth ⋮ The complexity of bicriteria tree-depth ⋮ On vertex rankings of graphs and its relatives
Cites Work
- On rigid circuit graphs
- Finding minimum height elimination trees for interval graphs in polynomial time
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- Incidence matrices and interval graphs
- Edge ranking of weighted trees
- The Role of Elimination Trees in Sparse Factorization
- Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
- Rankings of Graphs
