Graph spanners
David Peleg, Alejandro A. Schäffer · Journal of Graph Theory · 1989
Abstract Given a graph G = (V, E), a subgraph Gapos; = (V, Eapos;) is a t‐spanner of G if for every u, v ∈ V, the distance from u to v in Gapos; is at most t times longer than that distance in G. This paper presents some results concerning the existence and efficient constructability of sparse spanners for various classes of graphs, including general undirected graphs, undirected chordal graphs, and general directed graphs.
Cited by 422 works. doi:10.1002/jgt.3190130114
Authors
References
- Computers and Intractability: A Guide to the Theory of NP-Completeness
- An Introduction to the Theory of Numbers.
- Computational Geometry
- Algorithmic Graph Theory and Perfect Graphs
- Complexity of network synchronization
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- There is a planar graph almost as good as the complete graph
- A characterisation of rigid circuit graphs
- Delaunay graphs are almost as good as complete graphs
- Optimal simulations of tree machines