Spanners in graphs of bounded degree

Publisher Website
Google Scholar
Abstract
Given a graph G = (V, E), a subgraph S = (V, Es) 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.

This publication has 16 references indexed in Scilit: