A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2

Piotr Berman; Marek Karpinski; Alexander Zelikovsky

doi:10.1007/978-3-642-17517-6_4

A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2

Piotr Berman, Marek Karpinski, Alexander Zelikovsky

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.

Original language	English (US)
Title of host publication	Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings
Pages	15-24
Number of pages	10
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-17517-6_4
State	Published - 2010
Event	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 - Jeju Island, Korea, Republic of Duration: Dec 15 2010 → Dec 17 2010

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	6506 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	21st Annual International Symposium on Algorithms and Computations, ISAAC 2010
Country/Territory	Korea, Republic of
City	Jeju Island
Period	12/15/10 → 12/17/10

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-17517-6_4

Cite this

Berman, P., Karpinski, M., & Zelikovsky, A. (2010). A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings (PART 1 ed., pp. 15-24). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6506 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-17517-6_4

Berman, Piotr ; Karpinski, Marek ; Zelikovsky, Alexander. / A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2. Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 1. ed. 2010. pp. 15-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{101bc7d5aa1b489f92f09442d9e32ab8,

title = "A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2",

abstract = "Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.",

author = "Piotr Berman and Marek Karpinski and Alexander Zelikovsky",

note = "Funding Information: ★ Research partially done while visiting Department of Computer Science, University of Bonn and supported by DFG grant Bo 56/174-1. ★★Supported in part by DFG grants, Procope grant 31022, and the Hausdorff Center grant EXC59-1. ★★★ Supported in part by NSF grant IIS-0916948.; 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010 ; Conference date: 15-12-2010 Through 17-12-2010",

year = "2010",

doi = "10.1007/978-3-642-17517-6_4",

language = "English (US)",

isbn = "3642175163",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "15--24",

booktitle = "Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings",

edition = "PART 1",

}

Berman, P, Karpinski, M & Zelikovsky, A 2010, A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2. in Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 6506 LNCS, pp. 15-24, 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010, Jeju Island, Korea, Republic of, 12/15/10. https://doi.org/10.1007/978-3-642-17517-6_4

A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2. / Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander.
Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 1. ed. 2010. p. 15-24 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6506 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2

AU - Berman, Piotr

AU - Karpinski, Marek

AU - Zelikovsky, Alexander

N1 - Funding Information: ★ Research partially done while visiting Department of Computer Science, University of Bonn and supported by DFG grant Bo 56/174-1. ★★Supported in part by DFG grants, Procope grant 31022, and the Hausdorff Center grant EXC59-1. ★★★ Supported in part by NSF grant IIS-0916948.

PY - 2010

Y1 - 2010

N2 - Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.

AB - Given a graph with edge lengths and a set of pairs of vertices which should be connected (requirements) the Generalized Steiner Tree Problem (GSTP) asks for a minimum length subgraph that connects every requirement. For the Generalized Steiner Tree Problem restricted to complete graphs with edge lengths 1 and 2, we provide a 1.5-approximation algorithm. It is the first algorithm with the approximation ratio significantly better than 2 for a class of graphs for which GSTP is MAX SNP-hard.

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

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

U2 - 10.1007/978-3-642-17517-6_4

DO - 10.1007/978-3-642-17517-6_4

M3 - Conference contribution

AN - SCOPUS:78650852906

SN - 3642175163

SN - 9783642175169

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 15

EP - 24

BT - Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings

T2 - 21st Annual International Symposium on Algorithms and Computations, ISAAC 2010

Y2 - 15 December 2010 through 17 December 2010

ER -

Berman P, Karpinski M, Zelikovsky A. A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2. In Algorithms and Computation - 21st International Symposium, ISAAC 2010, Proceedings. PART 1 ed. 2010. p. 15-24. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-17517-6_4

A 3/2-approximation algorithm for generalized steiner trees in complete graphs with edge lengths 1 and 2

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this