Almost diameter of a house-hole-free graph in linear time via LexBFS

DOI10.1016/S0166-218X(99)00077-3zbMath0933.05143OpenAlexW1993222648MaRDI QIDQ1302159

Feodor F. Dragan

Publication date: 22 March 2000

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(99)00077-3

zbMATH Keywords

diametereccentricityasteroidal triple-free graphlinear-time algorithmlexicographic breadth-first searchhouse-hole-domino-free graphhouse-hole-free graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (10)

Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ The diameter of AT‐free graphs ⋮ A new characterization of HH-free graphs ⋮ End-vertices of LBFS of (AT-free) bigraphs ⋮ On end-vertices of lexicographic breadth first searches ⋮ Diameter determination on restricted graph families ⋮ On the power of BFS to determine a graph's diameter ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Computing Giant Graph Diameters

This page was built for publication: Almost diameter of a house-hole-free graph in linear time via LexBFS