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

DOI10.1016/S0166-218X(99)00077-3MaRDI QIDQ1302159zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Diameter determination on restricted graph families
• scientific article; zbMATH DE number 1262798
• scientific article; zbMATH DE number 2086230
• On the power of BFS to determine a graph's diameter
• Linear-time graph distance and diameter approximation

Cited in

(15)

• scientific article; zbMATH DE number 2086230 (Why is no real title available?)
• Vertex ordering characterizations of graphs of bounded asteroidal number
• Recognizing LBFS trees of bipartite graphs
• LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
• LexBFS-orderings and powers of graphs
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• On the power of BFS to determine a graph's diameter
• A new characterization of HH-free graphs
• Computing giant graph diameters
• Diameter determination on restricted graph families
• Beyond Helly graphs: the diameter problem on absolute retracts
• End-vertices of LBFS of (AT-free) bigraphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• On end-vertices of lexicographic breadth first searches
• The diameter of AT‐free graphs

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

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