Vertex ranking of asteroidal triple-free graphs

DOI10.1016/S0020-0190(98)00162-8zbMath1339.05395OpenAlexW2005655086MaRDI QIDQ293448

F. Blanchet-Sadri, M. Dambrine

Publication date: 9 June 2016

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

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098001628?np=y

zbMATH Keywords

graph algorithmsvertex rankingasteroidal triple-free graphminimal separator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (9)

An optimal parallel algorithm forc-vertex-ranking of trees ⋮ Constructing a minimum height elimination tree of a tree in linear time ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Rank numbers for bent ladders ⋮ Computing tree-depth faster than \(2^n\) ⋮ Optimal vertex ranking of block graphs ⋮ Rank numbers of grid graphs ⋮ Rank numbers for some trees and unicyclic graphs ⋮ Max-optimal and sum-optimal labelings of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• On a graph partition problem with application to VLSI layout
• Finding minimum height elimination trees for interval graphs in polynomial time
• Measuring the vulnerability for classes of intersection graphs
• Optimal node ranking of tree in linear time
• Ordered colourings
• Representation of a finite graph by a set of intervals on the real line
• The Role of Elimination Trees in Sparse Factorization
• The Multifrontal Solution of Indefinite Sparse Symmetric Linear
• The Complexity of the Partial Order Dimension Problem
• Asteroidal Triple-Free Graphs
• Listing all Minimal Separators of a Graph
• Rankings of Graphs
• Treewidth and Pathwidth of Permutation Graphs

This page was built for publication: Vertex ranking of asteroidal triple-free graphs