Diameter determination on restricted graph families
From MaRDI portal
Publication:5951960
DOI10.1016/S0166-218X(00)00281-XzbMath0990.05119MaRDI QIDQ5951960
Feodor F. Dragan, Christophe Paul, Michel A. Habib, Derek Gordon Corneil
Publication date: 14 August 2002
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
05C90: Applications of graph theory
68R10: Graph theory (including graph drawing) in computer science
Related Items
On the power of BFS to determine a graph's diameter, Eccentricity, center and radius computations on the cover graphs of distributive lattices with applications to stable matchings, On computing the diameter of real-world undirected graphs, On end-vertices of lexicographic breadth first searches, Fast diameter and radius BFS-based computation in (weakly connected) real-world graphs, Computing Giant Graph Diameters, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number
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
