File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Spanners with slack

TitleSpanners with slack
Authors
KeywordsComputational Complexity
Distance Measurement
Edge Detection
Problem Solving
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. 4168 LNCS, p. 196-207 How to Cite?
AbstractGiven a metric (V, d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion. In this paper, we study the problem of spanners with slack: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a small constant fraction of the distances, but are then required to incur only a constant (independent of n) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into ℓ p spaces. For instance, we show that if we ignore an e fraction of the distances, we can get spanners with O(n) edges and O(log 1/ε) distortion for the remaining distances. We also show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. This paper complements similar results obtained in recent research on slack embeddings into normed metric spaces. © Springer-Verlag Berlin Heidelberg 2006.
Persistent Identifierhttp://hdl.handle.net/10722/92645
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorChan, THHen_HK
dc.contributor.authorDinitz, Men_HK
dc.contributor.authorGupta, Aen_HK
dc.date.accessioned2010-09-17T10:52:53Z-
dc.date.available2010-09-17T10:52:53Z-
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. 4168 LNCS, p. 196-207en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/92645-
dc.description.abstractGiven a metric (V, d), a spanner is a sparse graph whose shortest-path metric approximates the distance d to within a small multiplicative distortion. In this paper, we study the problem of spanners with slack: e.g., can we find sparse spanners where we are allowed to incur an arbitrarily large distortion on a small constant fraction of the distances, but are then required to incur only a constant (independent of n) distortion on the remaining distances? We answer this question in the affirmative, thus complementing similar recent results on embeddings with slack into ℓ p spaces. For instance, we show that if we ignore an e fraction of the distances, we can get spanners with O(n) edges and O(log 1/ε) distortion for the remaining distances. We also show how to obtain sparse and low-weight spanners with slack from existing constructions of conventional spanners, and these techniques allow us to also obtain the best known results for distance oracles and distance labelings with slack. This paper complements similar results obtained in recent research on slack embeddings into normed metric spaces. © 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.subjectComputational Complexityen_HK
dc.subjectDistance Measurementen_HK
dc.subjectEdge Detectionen_HK
dc.subjectProblem Solvingen_HK
dc.titleSpanners with slacken_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-33750739218en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-33750739218&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume4168 LNCSen_HK
dc.identifier.spage196en_HK
dc.identifier.epage207en_HK
dc.identifier.eissn1611-3349-
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChan, THH=12645073600en_HK
dc.identifier.scopusauthoridDinitz, M=15055654100en_HK
dc.identifier.scopusauthoridGupta, A=8354044800en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats