1.25-approximation algorithm for steiner tree problem with distances 1 and 2

Piotr Berman; Marek Karpinski; Alexander Zelikovsky

doi:10.1007/978-3-642-03367-4_8

1.25-approximation algorithm for steiner tree problem with distances 1 and 2

Piotr Berman, Marek Karpinski, Alexander Zelikovsky

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

9 Scopus citations

Abstract

Given a connected graph G = (V,E) with nonnegative costs on edges, , and a subset of terminal nodes R ⊂ V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279.

Original language	English (US)
Title of host publication	Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings
Pages	86-97
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-03367-4_8
State	Published - 2009
Event	11th International Symposium on Algorithms and Data Structures, WADS 2009 - Banff, AB, Canada Duration: Aug 21 2009 → Aug 23 2009

Publication series

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

Other

Other	11th International Symposium on Algorithms and Data Structures, WADS 2009
Country/Territory	Canada
City	Banff, AB
Period	8/21/09 → 8/23/09

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/978-3-642-03367-4_8

Cite this

Berman, P., Karpinski, M., & Zelikovsky, A. (2009). 1.25-approximation algorithm for steiner tree problem with distances 1 and 2. In Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings (pp. 86-97). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5664 LNCS). https://doi.org/10.1007/978-3-642-03367-4_8

Berman, Piotr ; Karpinski, Marek ; Zelikovsky, Alexander. / 1.25-approximation algorithm for steiner tree problem with distances 1 and 2. Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. 2009. pp. 86-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{4a736c9ba0294d4ab68d36449122d43a,

title = "1.25-approximation algorithm for steiner tree problem with distances 1 and 2",

abstract = "Given a connected graph G = (V,E) with nonnegative costs on edges, , and a subset of terminal nodes R ⊂ V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279.",

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

year = "2009",

doi = "10.1007/978-3-642-03367-4_8",

language = "English (US)",

isbn = "3642033660",

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

pages = "86--97",

booktitle = "Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings",

note = "11th International Symposium on Algorithms and Data Structures, WADS 2009 ; Conference date: 21-08-2009 Through 23-08-2009",

}

Berman, P, Karpinski, M & Zelikovsky, A 2009, 1.25-approximation algorithm for steiner tree problem with distances 1 and 2. in Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5664 LNCS, pp. 86-97, 11th International Symposium on Algorithms and Data Structures, WADS 2009, Banff, AB, Canada, 8/21/09. https://doi.org/10.1007/978-3-642-03367-4_8

1.25-approximation algorithm for steiner tree problem with distances 1 and 2. / Berman, Piotr; Karpinski, Marek; Zelikovsky, Alexander.
Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. 2009. p. 86-97 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5664 LNCS).

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

TY - GEN

T1 - 1.25-approximation algorithm for steiner tree problem with distances 1 and 2

AU - Berman, Piotr

AU - Karpinski, Marek

AU - Zelikovsky, Alexander

PY - 2009

Y1 - 2009

N2 - Given a connected graph G = (V,E) with nonnegative costs on edges, , and a subset of terminal nodes R ⊂ V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279.

AB - Given a connected graph G = (V,E) with nonnegative costs on edges, , and a subset of terminal nodes R ⊂ V, the Steiner tree problem asks for the minimum cost subgraph of G spanning R. The Steiner Tree Problem with distances 1 and 2 (i.e., when the cost of any edge is either 1 or 2) has been investigated for long time since it is MAX SNP-hard and admits better approximations than the general problem. We give a 1.25 approximation algorithm for the Steiner Tree Problem with distances 1 and 2, improving on the previously best known ratio of 1.279.

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

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

U2 - 10.1007/978-3-642-03367-4_8

DO - 10.1007/978-3-642-03367-4_8

M3 - Conference contribution

AN - SCOPUS:69949120137

SN - 3642033660

SN - 9783642033667

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

SP - 86

EP - 97

BT - Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings

T2 - 11th International Symposium on Algorithms and Data Structures, WADS 2009

Y2 - 21 August 2009 through 23 August 2009

ER -

Berman P, Karpinski M, Zelikovsky A. 1.25-approximation algorithm for steiner tree problem with distances 1 and 2. In Algorithms and Data Structures - 11th International Symposium, WADS 2009, Proceedings. 2009. p. 86-97. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-03367-4_8

1.25-approximation algorithm for steiner tree problem with distances 1 and 2

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this