Premium
Graph spanners
Author(s) -
Peleg David,
Schäffer Alejandro A.
Publication year - 1989
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190130114
Subject(s) - combinatorics , mathematics , chordal graph , undirected graph , block graph , discrete mathematics , graph , 1 planar graph
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.