File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A tight lower bound for the steiner point removal problem on trees

TitleA tight lower bound for the steiner point removal problem on trees
Authors
KeywordsAlgorithms
Problem Solving
Set Theory
Issue Date2006
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2006, v. 4110 LNCS, p. 70-81 How to Cite?
AbstractGupta (SODA'01) considered the Steiner Point Removal (SPR) problem on trees. Given an edge-weighted tree T and a subset 5 of vertices called terminals in the tree, find an edge-weighted tree T S on the vertex set S such that the distortion of the distances between vertices in S is small. His algorithm guarantees that for any finite tree, the distortion incurred is at most 8. Moreover, a family of trees, where the leaves are the terminals, is presented such that the distortion incurred by any algorithm for SPR is at least 4(1 -o(1)). In this paper, we close the gap and show that the upper bound 8 is essentially tight. In particular, for complete binary trees in which all edges have unit weight, we show that the distortion incurred by any algorithm for the SPR problem must be at least 8(1 -o(1)). © Springer-Verlag Berlin Heidelberg 2006.
Persistent Identifierhttp://hdl.handle.net/10722/92658
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorXia, Den_HK
dc.contributor.authorKonjevod, Gen_HK
dc.contributor.authorRicha, Aen_HK
dc.date.accessioned2010-09-17T10:53:16Z-
dc.date.available2010-09-17T10:53:16Z-
dc.date.issued2006en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2006, v. 4110 LNCS, p. 70-81en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92658-
dc.description.abstractGupta (SODA'01) considered the Steiner Point Removal (SPR) problem on trees. Given an edge-weighted tree T and a subset 5 of vertices called terminals in the tree, find an edge-weighted tree T S on the vertex set S such that the distortion of the distances between vertices in S is small. His algorithm guarantees that for any finite tree, the distortion incurred is at most 8. Moreover, a family of trees, where the leaves are the terminals, is presented such that the distortion incurred by any algorithm for SPR is at least 4(1 -o(1)). In this paper, we close the gap and show that the upper bound 8 is essentially tight. In particular, for complete binary trees in which all edges have unit weight, we show that the distortion incurred by any algorithm for the SPR problem must be at least 8(1 -o(1)). © Springer-Verlag Berlin Heidelberg 2006.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.subjectAlgorithmsen_HK
dc.subjectProblem Solvingen_HK
dc.subjectSet Theoryen_HK
dc.titleA tight lower bound for the steiner point removal problem on treesen_HK
dc.typeArticleen_HK
dc.identifier.emailChan, THH:hubert@cs.hku.hken_HK
dc.identifier.authorityChan, THH=rp01312en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-33750036089en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33750036089&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4110 LNCSen_HK
dc.identifier.spage70en_HK
dc.identifier.epage81en_HK
dc.identifier.eissn1611-3349-
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridXia, D=14029250800en_HK
dc.identifier.scopusauthoridKonjevod, G=6602226952en_HK
dc.identifier.scopusauthoridRicha, A=6603231715en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats