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

DOI10.1016/S0166-218X(99)00157-2zbMath0940.05024MaRDI QIDQ1962066

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 theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Graph extremities defined by search algorithms ⋮ Finding a sun in building-free graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ \(L(2,1)\)-labeling of perfect elimination bipartite graphs ⋮ The \(b\)-\textsc{Matching} problem in distance-hereditary graphs and beyond ⋮ End-vertices of LBFS of (AT-free) bigraphs ⋮ Diameter determination on restricted graph families ⋮ Unnamed Item ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Minimum Eccentricity Shortest Paths in Some Structured Graph Classes ⋮ Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs ⋮ Eccentricity function in distance-hereditary graphs ⋮ Voronoi Diagrams on Planar Graphs, and Computing the Diameter in Deterministic $\tilde{O}(n^{5/3})$ Time

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Completely separable graphs
• Distance-hereditary graphs
• Pseudo-modular graphs
• Some aspects of the semi-perfect elimination
• LexBFS-orderings and powers of chordal graphs
• Perfect elimination orderings of chordal powers of graphs
• On the semi-perfect elimination
• Powers of distance-hereditary graphs
• Distance-Hereditary Graphs, Steiner Trees, and Connected Domination
• Algorithmic Aspects of Vertex Elimination on Graphs
• A CHARACTERIZATION OF DISTANCE-HEREDITARY GRAPHS
• Convexity and HHD-Free Graphs
• Dominating cliques in distance-hereditary graphs

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