Some new structural properties of shortest 2-connected steiner networks

Shuying Peng; Meili Li; Shenggui Zhang; T. C.Edwin Cheng

doi:10.1007/978-3-540-73814-5_31

Some new structural properties of shortest 2-connected steiner networks

Shuying Peng, Meili Li, Shenggui Zhang, T. C.Edwin Cheng

School of Mathematics and Statistics

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

Abstract

In this paper we give a number of structural results for the problem of constructing minimum-weight 2-connected Steiner networks for a set of terminals in a graph and in the plane. A sufficient condition for a minimum-weight 2-connected Steiner network on a set of points in the plane to be basic is also obtained. Using the structural results, we show that the minimum-weight 2-connected Steiner network on a set of terminals Z is either a minimum-weight 2-connected spanning network on Z or isomorphic to one of several specific networks when |Z| = 6 or 7.

Original language	English
Title of host publication	Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings
Publisher	Springer Verlag
Pages	317-324
Number of pages	8
ISBN (Print)	9783540738138
DOIs	https://doi.org/10.1007/978-3-540-73814-5_31
State	Published - 2007
Event	1st International Frontiers in Algorithmics Workshop, FAW 2007 - Lanzhou, China Duration: 1 Aug 2007 → 3 Aug 2007

Publication series

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

Conference

Conference	1st International Frontiers in Algorithmics Workshop, FAW 2007
Country/Territory	China
City	Lanzhou
Period	1/08/07 → 3/08/07

Access to Document

10.1007/978-3-540-73814-5_31

Cite this

Peng, S., Li, M., Zhang, S., & Cheng, T. C. E. (2007). Some new structural properties of shortest 2-connected steiner networks. In Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings (pp. 317-324). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4613 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-73814-5_31

Peng, Shuying ; Li, Meili ; Zhang, Shenggui et al. / Some new structural properties of shortest 2-connected steiner networks. Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings. Springer Verlag, 2007. pp. 317-324 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ad5648090d6a43449e76683206d7059c,

title = "Some new structural properties of shortest 2-connected steiner networks",

abstract = "In this paper we give a number of structural results for the problem of constructing minimum-weight 2-connected Steiner networks for a set of terminals in a graph and in the plane. A sufficient condition for a minimum-weight 2-connected Steiner network on a set of points in the plane to be basic is also obtained. Using the structural results, we show that the minimum-weight 2-connected Steiner network on a set of terminals Z is either a minimum-weight 2-connected spanning network on Z or isomorphic to one of several specific networks when |Z| = 6 or 7.",

author = "Shuying Peng and Meili Li and Shenggui Zhang and Cheng, {T. C.Edwin}",

year = "2007",

doi = "10.1007/978-3-540-73814-5_31",

language = "英语",

isbn = "9783540738138",

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

publisher = "Springer Verlag",

pages = "317--324",

booktitle = "Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings",

note = "1st International Frontiers in Algorithmics Workshop, FAW 2007 ; Conference date: 01-08-2007 Through 03-08-2007",

}

Peng, S, Li, M, Zhang, S & Cheng, TCE 2007, Some new structural properties of shortest 2-connected steiner networks. in Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4613 LNCS, Springer Verlag, pp. 317-324, 1st International Frontiers in Algorithmics Workshop, FAW 2007, Lanzhou, China, 1/08/07. https://doi.org/10.1007/978-3-540-73814-5_31

Some new structural properties of shortest 2-connected steiner networks. / Peng, Shuying; Li, Meili; Zhang, Shenggui et al.
Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings. Springer Verlag, 2007. p. 317-324 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4613 LNCS).

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

TY - GEN

T1 - Some new structural properties of shortest 2-connected steiner networks

AU - Peng, Shuying

AU - Li, Meili

AU - Zhang, Shenggui

AU - Cheng, T. C.Edwin

PY - 2007

Y1 - 2007

N2 - In this paper we give a number of structural results for the problem of constructing minimum-weight 2-connected Steiner networks for a set of terminals in a graph and in the plane. A sufficient condition for a minimum-weight 2-connected Steiner network on a set of points in the plane to be basic is also obtained. Using the structural results, we show that the minimum-weight 2-connected Steiner network on a set of terminals Z is either a minimum-weight 2-connected spanning network on Z or isomorphic to one of several specific networks when |Z| = 6 or 7.

AB - In this paper we give a number of structural results for the problem of constructing minimum-weight 2-connected Steiner networks for a set of terminals in a graph and in the plane. A sufficient condition for a minimum-weight 2-connected Steiner network on a set of points in the plane to be basic is also obtained. Using the structural results, we show that the minimum-weight 2-connected Steiner network on a set of terminals Z is either a minimum-weight 2-connected spanning network on Z or isomorphic to one of several specific networks when |Z| = 6 or 7.

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

U2 - 10.1007/978-3-540-73814-5_31

DO - 10.1007/978-3-540-73814-5_31

M3 - 会议稿件

AN - SCOPUS:38049101316

SN - 9783540738138

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

SP - 317

EP - 324

BT - Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings

PB - Springer Verlag

T2 - 1st International Frontiers in Algorithmics Workshop, FAW 2007

Y2 - 1 August 2007 through 3 August 2007

ER -

Peng S, Li M, Zhang S, Cheng TCE. Some new structural properties of shortest 2-connected steiner networks. In Frontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings. Springer Verlag. 2007. p. 317-324. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-73814-5_31

Some new structural properties of shortest 2-connected steiner networks

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this