Generating low-degree 2-spanners

Research output: Contribution to journalArticle

21 Citations (Scopus)

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 - Jan 1 1998
Externally publishedYes

Fingerprint

Spanners
Spanner
Approximation algorithms
Derandomization
Probabilistic Algorithms
Set Cover
Sparse Graphs
Randomized Algorithms
Maximum Degree
Undirected Graph
Connected graph
Approximation Algorithms
Subgraph
Subset
Approximation
Graph in graph theory

All Science Journal Classification (ASJC) codes

  • Mathematics(all)
  • Computer Science(all)

Cite this

Kortsarz, Guy. / Generating low-degree 2-spanners. In: SIAM Journal on Computing. 1998 ; Vol. 27, No. 5. pp. 1438-1456.
@article{1631459def104266996e6bb4b3dff65a,
title = "Generating low-degree 2-spanners",
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 {\~O}(Δ1/4). We then present a probabilistic algorithm that is more efficient for sparse graphs. Our algorithms are converted into deterministic ones using derandomization.",
author = "Guy Kortsarz",
year = "1998",
month = "1",
day = "1",
doi = "https://doi.org/10.1137/S0097539794268753",
language = "English (US)",
volume = "27",
pages = "1438--1456",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "5",

}

Generating low-degree 2-spanners. / Kortsarz, Guy.

In: SIAM Journal on Computing, Vol. 27, No. 5, 01.01.1998, p. 1438-1456.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Generating low-degree 2-spanners

AU - Kortsarz, Guy

PY - 1998/1/1

Y1 - 1998/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0346181207&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0346181207&partnerID=8YFLogxK

U2 - https://doi.org/10.1137/S0097539794268753

DO - https://doi.org/10.1137/S0097539794268753

M3 - Article

VL - 27

SP - 1438

EP - 1456

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 5

ER -