Contributor(s)The Pennsylvania State University CiteSeerX Archives
Full recordShow full item record
AbstractA k\Gammaspanner of a connected graph G = (V; E) is a subgraph G 0 consisting of all the vertices of V and a subset of the edges, with the additional property that the distance between any two vertices in G 0 is larger than the distance in G by no more than a factor of k. This paper concerns the hardness of finding spanners with a number of edges close to the optimum. It is proved that for every fixed k, approximating the spanner problem is at least as hard as approximating the set cover problem We also consider a weighted version of the spanner problem, and prove an essential difference between the approximability of the case k = 2, and the case k 5. Department of Computer Science, The Open University, 16 Klauzner st., Ramat Aviv, Israel, email@example.com. 1 Introduction The concept of graph spanners has been studied in several recent papers in the context of communication networks, distributed computing, robotics and computational geometry [ADDJ-90, C-94, CK-94,...