Some new structural properties of shortest 2-connected steiner networks

Shuying Peng, Meili Li, Shenggui Zhang, Edwin Tai Chiu Cheng

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-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 languageEnglish
Title of host publicationFrontiers in Algorithmics - First Annual International Workshop, FAW 2007, Proceedings
Pages317-324
Number of pages8
Publication statusPublished - 1 Dec 2007
Event1st International Frontiers in Algorithmics Workshop, FAW 2007 - Lanzhou, China
Duration: 1 Aug 20073 Aug 2007

Publication series

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

Conference

Conference1st International Frontiers in Algorithmics Workshop, FAW 2007
CountryChina
CityLanzhou
Period1/08/073/08/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this