TY - GEN
T1 - Some new structural properties of shortest 2-connected steiner networks
AU - Peng, Shuying
AU - Li, Meili
AU - Zhang, Shenggui
AU - Cheng, Edwin Tai Chiu
PY - 2007/12/1
Y1 - 2007/12/1
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
M3 - Conference article published in proceeding or book
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
T2 - 1st International Frontiers in Algorithmics Workshop, FAW 2007
Y2 - 1 August 2007 through 3 August 2007
ER -