File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Article: A tight lower bound for the steiner point removal problem on trees
Title  A tight lower bound for the steiner point removal problem on trees 

Authors  
Keywords  Algorithms Problem Solving Set Theory 
Issue Date  2006 
Publisher  Springer 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. 7081 How to Cite? 
Abstract  Gupta (SODA'01) considered the Steiner Point Removal (SPR) problem on trees. Given an edgeweighted tree T and a subset 5 of vertices called terminals in the tree, find an edgeweighted 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)). © SpringerVerlag Berlin Heidelberg 2006. 
Persistent Identifier  http://hdl.handle.net/10722/92658 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Chan, THH  en_HK 
dc.contributor.author  Xia, D  en_HK 
dc.contributor.author  Konjevod, G  en_HK 
dc.contributor.author  Richa, A  en_HK 
dc.date.accessioned  20100917T10:53:16Z   
dc.date.available  20100917T10:53:16Z   
dc.date.issued  2006  en_HK 
dc.identifier.citation  Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2006, v. 4110 LNCS, p. 7081  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/92658   
dc.description.abstract  Gupta (SODA'01) considered the Steiner Point Removal (SPR) problem on trees. Given an edgeweighted tree T and a subset 5 of vertices called terminals in the tree, find an edgeweighted 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)). © SpringerVerlag Berlin Heidelberg 2006.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)  en_HK 
dc.subject  Algorithms  en_HK 
dc.subject  Problem Solving  en_HK 
dc.subject  Set Theory  en_HK 
dc.title  A tight lower bound for the steiner point removal problem on trees  en_HK 
dc.type  Article  en_HK 
dc.identifier.email  Chan, THH:hubert@cs.hku.hk  en_HK 
dc.identifier.authority  Chan, THH=rp01312  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.scopus  eid_2s2.033750036089  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.033750036089&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  4110 LNCS  en_HK 
dc.identifier.spage  70  en_HK 
dc.identifier.epage  81  en_HK 
dc.identifier.eissn  16113349   
dc.publisher.place  Germany  en_HK 
dc.identifier.scopusauthorid  Chan, THH=12645073600  en_HK 
dc.identifier.scopusauthorid  Xia, D=14029250800  en_HK 
dc.identifier.scopusauthorid  Konjevod, G=6602226952  en_HK 
dc.identifier.scopusauthorid  Richa, A=6603231715  en_HK 