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)

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

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)

Cites Work

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

Cited In (22)

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

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)