A PTAS for weight constrained Steiner trees in series-parallel graphs

Guangting Chen; Guoliang Xue

doi:10.1016/S0304-3975(03)00088-4

A PTAS for weight constrained Steiner trees in series-parallel graphs

Guangting Chen
, Guoliang Xue

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

10 Scopus citations

Abstract

A study was performed on a PTAS for weight constrained Steiner trees in series-parallel graphs. A strongly polynomial time approximation scheme for the NP-complete problem was presented. It was found that weight constrained minimum cost Steiner tree problem (WCSTP) was NP-hard even when the graph was an S-P graph.

Original language	English (US)
Pages (from-to)	237-247
Number of pages	11
Journal	Theoretical Computer Science
Volume	304
Issue number	1-3
DOIs	https://doi.org/10.1016/S0304-3975(03)00088-4
State	Published - Jul 28 2003

Keywords

Multiple constraints quality of service
Series-parallel graphs
Steiner trees

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/S0304-3975(03)00088-4

Cite this

@article{45d1298cbed345db8ac0d1889c0ed038,

title = "A PTAS for weight constrained Steiner trees in series-parallel graphs",

abstract = "A study was performed on a PTAS for weight constrained Steiner trees in series-parallel graphs. A strongly polynomial time approximation scheme for the NP-complete problem was presented. It was found that weight constrained minimum cost Steiner tree problem (WCSTP) was NP-hard even when the graph was an S-P graph.",

keywords = "Multiple constraints quality of service, Series-parallel graphs, Steiner trees",

author = "Guangting Chen and Guoliang Xue",

note = "Funding Information: ∗Corresponding author. E-mail addresses: [email protected] (Guangting Chen), [email protected] (Guoliang Xue). 1Supported in part by Chinese NSF grant CNSF19971078 and Chinese Institute of Electronic Science grant 57-7-3-7. 2Supported in part by ARO grant DAAD19-00-1-0377 and by DOE grant DE-FG02-00ER45828. A preliminary version of this paper was presented at COCOON{\textquoteright}01 where we presented a PTAS whose running time also depends on the input size of the problem.",

year = "2003",

month = jul,

day = "28",

doi = "10.1016/S0304-3975(03)00088-4",

language = "English (US)",

volume = "304",

pages = "237--247",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

T1 - A PTAS for weight constrained Steiner trees in series-parallel graphs

AU - Chen, Guangting

AU - Xue, Guoliang

N1 - Funding Information: ∗Corresponding author. E-mail addresses: [email protected] (Guangting Chen), [email protected] (Guoliang Xue). 1Supported in part by Chinese NSF grant CNSF19971078 and Chinese Institute of Electronic Science grant 57-7-3-7. 2Supported in part by ARO grant DAAD19-00-1-0377 and by DOE grant DE-FG02-00ER45828. A preliminary version of this paper was presented at COCOON’01 where we presented a PTAS whose running time also depends on the input size of the problem.

PY - 2003/7/28

Y1 - 2003/7/28

N2 - A study was performed on a PTAS for weight constrained Steiner trees in series-parallel graphs. A strongly polynomial time approximation scheme for the NP-complete problem was presented. It was found that weight constrained minimum cost Steiner tree problem (WCSTP) was NP-hard even when the graph was an S-P graph.

AB - A study was performed on a PTAS for weight constrained Steiner trees in series-parallel graphs. A strongly polynomial time approximation scheme for the NP-complete problem was presented. It was found that weight constrained minimum cost Steiner tree problem (WCSTP) was NP-hard even when the graph was an S-P graph.

KW - Multiple constraints quality of service

KW - Series-parallel graphs

KW - Steiner trees

UR - https://www.scopus.com/pages/publications/0037811195

UR - https://www.scopus.com/pages/publications/0037811195#tab=citedBy

U2 - 10.1016/S0304-3975(03)00088-4

DO - 10.1016/S0304-3975(03)00088-4

M3 - Article

AN - SCOPUS:0037811195

SN - 0304-3975

VL - 304

SP - 237

EP - 247

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 1-3

ER -

A PTAS for weight constrained Steiner trees in series-parallel graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this