Generating low-degree 2-spanners

Research output: Contribution to journalArticlepeer-review

26 Scopus citations

Abstract

This research was supported in part by a Walter and 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 Õ(Δ1/4). We then present a probabilistic algorithm that is more efficient for sparse graphs. Our algorithms are converted into deterministic ones using derandomization.

Original languageEnglish (US)
Pages (from-to)1438-1456
Number of pages19
JournalSIAM Journal on Computing
Volume27
Issue number5
DOIs
StatePublished - 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Approximation
  • Graph spanners
  • Np-hardness
  • Randomized rounding

Fingerprint

Dive into the research topics of 'Generating low-degree 2-spanners'. Together they form a unique fingerprint.

Cite this