RESTRICTIONS OF MINIMUM SPANNER PROBLEMS

A t-spanner of a graph G is a spanning subgraph H such that the distan ce between any two vertices in H is at most t times their distance in G. Spanners arise in the context of approximating the original graph w ith a sparse subgraph (Peleg, D., and Schaffer, A. A. (1989), J. Graph . Theory 13 (1), 99-116). The MINIMUM t-SPANNER problem seeks to find a t-spanner with the minimum number of edges for the given graph. In t his paper, we completely settle the complexity status of this problem for various values of t, on chordal graphs, split graphs, bipartite gr aphs and convex bipartite graphs. Our results settle an open question raised by L. Cai (1994, Discrete Appl. Math. 48, 187-194) and also gre atly simplify some of the proofs presented by Cai and by L. Cai and M. Keil (1994, Networks 24, 233-249). We also give a factor 2 approximat ion algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Fi nally, we provide approximation algorithms for the bandwidth minimizat ion problem on convex bipartite graphs and split graphs using the noti on of tree spanners. (C) 1997 Academic Press.