Generating Low-Degree 2-Spanners

Publisher Website
Google Scholar
Abstract
A k-spanner of a connected (undirected unweighted) graph G = (V,E) is a subgraph G' 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' is larger than that distance in G by no more than a factor of k. This paper is concerned with approximating the problem of finding a 2-spanner in a given graph, with minimum maximum degree. We first show that the problem is at least as hard to approximate as set cover. Then a randomized approximation algorithm is provided for this problem, with approximation ratio of (O) over tilde(Delta(1/4)). We then present a probabilistic algorithm that is more efficient for sparse graphs. Our algorithms are converted into deterministic ones using derandomization.

This publication has 18 references indexed in Scilit: