Restrictions of Minimum Spanner Problems |
| |
Authors: | G. Venkatesan U. Rotics M.S. Madanlal J.A. Makowsky C.Pandu Rangan |
| |
Affiliation: | aDepartment of Computer Science and Engineering, Indian Institute of Technology, Madras, 600036, India;bDepartment of Computer Science, Technion–Israel Institute of Technology, 32000, Haifa, Israel |
| |
Abstract: | At-spanner of a graphGis a spanning subgraphHsuch that the distance between any two vertices inHis at mostttimes their distance inG. Spanners arise in the context of approximating the original graph with a sparse subgraph (Peleg, D., and Schäffer, A. A. (1989),J. Graph. Theory13(1), 99–116). The MINIMUMt-SPANNER problem seeks to find at-spanner with the minimum number of edges for the given graph. In this paper, we completely settle the complexity status of this problem for various values oft, on chordal graphs, split graphs, bipartite graphs and convex bipartite graphs. Our results settle an open question raised by L. Cai (1994,Discrete Appl. Math.48, 187–194) and also greatly simplify some of the proofs presented by Cai and by L. Cai and M. Keil (1994,Networks24, 233–249). We also give a factor 2 approximation algorithm for the MINIMUM 2-SPANNER problem on interval graphs. Finally, we provide approximation algorithms for the bandwidth minimization problem on convex bipartite graphs and split graphs using the notion of tree spanners. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|