Premium
Spanners in graphs of bounded degree
Author(s) -
Cai Leizhen,
Keil Mark
Publication year - 1994
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230240406
Subject(s) - combinatorics , spanner , mathematics , bounded function , degree (music) , graph , discrete mathematics , partition (number theory) , graph factorization , computation , graph power , line graph , computer science , algorithm , acoustics , mathematical analysis , distributed computing , physics
Abstract Given a graph G = ( V, E ), a subgraph S = ( V, E s ) is a t ‐spanner of G if for every edge xy ϵ E the distance between x and y in S is at most t . Spanners have applications in communication networks, distributed systems, parallel computation, and many other areas. This paper is concerned with the complexity of finding a minimum size t ‐spanner in a graph with bounded degree. A linear time algorithm is presented for finding a minimum‐size 2‐spanner in any graph whose maximum degree is at most four. The algorithm is based on a graph theoretical result concerning edge partition of a graph into a “triangle‐free component” and “triangular‐components.” On the other hand, it is shown that to determine whether a graph with maximum degree at most nine contains a t ‐spanner with at most K edges ( K is given) is NP‐complete for any fixed t ⩾ 2. © 1994 by John Wiley & Sons, Inc.