File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: New bounds for multi-label interval routing

TitleNew bounds for multi-label interval routing
Authors
KeywordsCompact routing
Computational complexity
Distributed systems
Graph theory
Interval routing
k-dominating set
Network protocols
Planar graphs
Issue Date2004
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs
Citation
Theoretical Computer Science, 2004, v. 310 n. 1-3, p. 61-77 How to Cite?
AbstractInterval routing (IR) is a space-efficient routing method for computer networks. For longest routing path analysis, researchers have focused on lower bounds for many years. For any n-node graph G of diameter D, there exists an upper bound of 2D for IR using one or more labels, and an upper bound of ⌈3/2D⌉ for IR using O(√nlogn) or more labels. We present two upper bounds in the first part of the paper. We show that for every integer i>0, every n-node graph of diameter D has a k-dominating set of size O( i+1√n) for k≤(1-1/3i)D. This result implies a new upper bound of ⌈(2-1/3i)D⌉ for IR using O( i+1√n) or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg to achieve an upper bound of (1+α)D for IR using O(n/D) or more labels, where α is any constant in (0,1). The second part of the paper offers some lower bounds for planar graphs. For any M-label interval routing scheme (M-IRS), where M=O(√n), we derive a lower bound of [(2M+1)/(2M)]D-1 on the longest path for M=O( 3√n), and a lower bound of [(2(1+δ)M+1)/(2(1+δ)M)]D, where δε(0,1], for M=O(n). The latter result implies a lower bound of Ω(√n) on the number of labels needed to achieve optimality. © 2003 Elsevier B.V. All rights reserved.
Persistent Identifierhttp://hdl.handle.net/10722/89082
ISSN
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 0.570
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorTse, SSHen_HK
dc.contributor.authorLau, FCMen_HK
dc.date.accessioned2010-09-06T09:52:10Z-
dc.date.available2010-09-06T09:52:10Z-
dc.date.issued2004en_HK
dc.identifier.citationTheoretical Computer Science, 2004, v. 310 n. 1-3, p. 61-77en_HK
dc.identifier.issn0304-3975en_HK
dc.identifier.urihttp://hdl.handle.net/10722/89082-
dc.description.abstractInterval routing (IR) is a space-efficient routing method for computer networks. For longest routing path analysis, researchers have focused on lower bounds for many years. For any n-node graph G of diameter D, there exists an upper bound of 2D for IR using one or more labels, and an upper bound of ⌈3/2D⌉ for IR using O(√nlogn) or more labels. We present two upper bounds in the first part of the paper. We show that for every integer i>0, every n-node graph of diameter D has a k-dominating set of size O( i+1√n) for k≤(1-1/3i)D. This result implies a new upper bound of ⌈(2-1/3i)D⌉ for IR using O( i+1√n) or more labels, where i is any positive integer constant. We apply the result by Kutten and Peleg to achieve an upper bound of (1+α)D for IR using O(n/D) or more labels, where α is any constant in (0,1). The second part of the paper offers some lower bounds for planar graphs. For any M-label interval routing scheme (M-IRS), where M=O(√n), we derive a lower bound of [(2M+1)/(2M)]D-1 on the longest path for M=O( 3√n), and a lower bound of [(2(1+δ)M+1)/(2(1+δ)M)]D, where δε(0,1], for M=O(n). The latter result implies a lower bound of Ω(√n) on the number of labels needed to achieve optimality. © 2003 Elsevier B.V. All rights reserved.en_HK
dc.languageengen_HK
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcsen_HK
dc.relation.ispartofTheoretical Computer Scienceen_HK
dc.rightsTheoretical Computer Science. Copyright © Elsevier BV.en_HK
dc.subjectCompact routingen_HK
dc.subjectComputational complexityen_HK
dc.subjectDistributed systemsen_HK
dc.subjectGraph theoryen_HK
dc.subjectInterval routingen_HK
dc.subjectk-dominating seten_HK
dc.subjectNetwork protocolsen_HK
dc.subjectPlanar graphsen_HK
dc.titleNew bounds for multi-label interval routingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0304-3975&volume=310&issue=1-3&spage=61&epage=77&date=2004&atitle=New+Bounds+for+Multi-label+Interval+Routingen_HK
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1016/S0304-3975(03)00318-9en_HK
dc.identifier.scopuseid_2-s2.0-0242440295en_HK
dc.identifier.hkuros92476en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0242440295&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume310en_HK
dc.identifier.issue1-3en_HK
dc.identifier.spage61en_HK
dc.identifier.epage77en_HK
dc.identifier.isiWOS:000187222600003-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridTse, SSH=7006643113en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK
dc.identifier.issnl0304-3975-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats