LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem

DOI10.1016/S0166-218X(99)00157-2zbMATH Open0940.05024MaRDI QIDQ1962066FDOQ1962066

Authors Feodor F. Dragan, Falk Nicolai 

Publication date 16 July 2000

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

zbMATH Keywords

diameterlinear time algorithmdistance-hereditary graphperfect elimination orderinglexicographic breadth-first-searchmetric power

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12)

Recommendations

• LexBFS-orderings and powers of chordal graphs
• On Distance-Preserving and Domination Elimination Orderings
• Powers of distance-hereditary graphs
• Lexbfs-orderings and powers of hhd-free graphs^∗
• Almost diameter of a house-hole-free graph in linear time via LexBFS

Cites work

• scientific article; zbMATH DE number 3889566 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 468643 (Why is no real title available?)
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Algorithmic Aspects of Vertex Elimination on Graphs
• Completely separable graphs
• Convexity and HHD-Free Graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Distance-hereditary graphs
• Dominating cliques in distance-hereditary graphs
• LexBFS-orderings and powers of chordal graphs
• On the semi-perfect elimination
• Perfect elimination orderings of chordal powers of graphs
• Powers of distance-hereditary graphs
• Pseudo-modular graphs
• Some aspects of the semi-perfect elimination

Cited in

(22)

• The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond
• Finding a sun in building-free graphs
• LexBFS-orderings and powers of chordal graphs
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Powers of distance-hereditary graphs
• LexBFS-orderings and powers of graphs
• Eccentricity function in distance-hereditary graphs
• Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
• \( \alpha_i\)-metric graphs: radius, diameter and all eccentricities
• Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs
• Graph extremities defined by search algorithms
• Distance problems within Helly graphs and \(k\)-Helly graphs
• \(L(2,1)\)-labeling of perfect elimination bipartite graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Diameter determination on restricted graph families
• End-vertices of LBFS of (AT-free) bigraphs
• Fast approximation of eccentricities and distances in hyperbolic graphs
• A story of diameter, radius, and (almost) Helly property
• On distance-preserving elimination orderings in graphs: complexity and algorithms
• Minimum eccentricity shortest paths in some structured graph classes
• scientific article; zbMATH DE number 7561384 (Why is no real title available?)
• Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs

This page was built for publication: LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem

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