Diameter determination on restricted graph families
From MaRDI portal
Publication:5951960
DOI10.1016/S0166-218X(00)00281-XzbMath0990.05119OpenAlexW2091612923MaRDI QIDQ5951960
Christophe Paul, Feodor F. Dragan, Michel A. Habib, Derek Gordon Corneil
Publication date: 14 August 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00281-x
Applications of graph theory (05C90) Graph theory (including graph drawing) in computer science (68R10)
Related Items (19)
Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings ⋮ Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ A faster diameter problem algorithm for a chordal graph, with a connection to its center problem ⋮ Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number ⋮ On computing the diameter of real-world undirected graphs ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ The diameter of AT‐free graphs ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ End-vertices of LBFS of (AT-free) bigraphs ⋮ On end-vertices of lexicographic breadth first searches ⋮ An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time ⋮ Unnamed Item ⋮ On the power of BFS to determine a graph's diameter ⋮ Fast approximation of eccentricities and distances in hyperbolic graphs ⋮ Computing Giant Graph Diameters ⋮ Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs ⋮ Fast Diameter Computation within Split Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Characterizations of strongly chordal graphs
- Computation of the center and diameter of outerplanar graphs
- A recognition algorithm for the intersection graphs of directed paths in directed trees
- Almost diameter of a house-hole-free graph in linear time via LexBFS
- Unified all-pairs shortest path algorithms in the chordal hierarchy
- The algorithmic use of hypertree structure and maximum neighbourhood orderings
- On the semi-perfect elimination
- A characterisation of rigid circuit graphs
- LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Representation of a finite graph by a set of intervals on the real line
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- A simple linear-time algorithm for computing the center of an interval graph
- Algorithmic Aspects of Vertex Elimination on Graphs
- Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
- Linear Time Algorithms for Dominating Pairs in Asteroidal Triple-free Graphs
- Asteroidal Triple-Free Graphs
- Dominating cliques in distance-hereditary graphs
This page was built for publication: Diameter determination on restricted graph families
