File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: On the space requirement of interval routing

TitleOn the space requirement of interval routing
Authors
Issue Date1999
PublisherI E E E. The Journal's web site is located at http://www.computer.org/tc
Citation
Ieee Transactions On Computers, 1999, v. 48 n. 7, p. 752-757 How to Cite?
AbstractInterval routing is a space-efficient method for point-to-point networks. It is based on labeling the edges of a network with intervals of vertex numbers (called interval labels). An M-label scheme allows up to M labels to be attached on an edge. For arbitrary graphs of size n, n the number of vertices, the problem is to determine the minimum M necessary for achieving optimality in the length of the longest routing path. The longest routing path resulted from a labeling is an important indicator of the performance of any algorithm that runs on the network. We prove that there exists a graph with D = Ω(n1/3) such that if M ≤ n/18D - O(√n/D), the longest path is no shorter than D + Θ(D/√M). As a result, for any M-label IRS, if the longest path is to be shorter than D + Θ(D/√M), at least M = Ω(n/D) labels per edge would be necessary.
Persistent Identifierhttp://hdl.handle.net/10722/43649
ISSN
2015 Impact Factor: 1.723
2015 SCImago Journal Rankings: 0.924
ISI Accession Number ID
References

 

DC FieldValueLanguage
dc.contributor.authorTse, SSHen_HK
dc.contributor.authorLau, FCMen_HK
dc.date.accessioned2007-03-23T04:51:14Z-
dc.date.available2007-03-23T04:51:14Z-
dc.date.issued1999en_HK
dc.identifier.citationIeee Transactions On Computers, 1999, v. 48 n. 7, p. 752-757en_HK
dc.identifier.issn0018-9340en_HK
dc.identifier.urihttp://hdl.handle.net/10722/43649-
dc.description.abstractInterval routing is a space-efficient method for point-to-point networks. It is based on labeling the edges of a network with intervals of vertex numbers (called interval labels). An M-label scheme allows up to M labels to be attached on an edge. For arbitrary graphs of size n, n the number of vertices, the problem is to determine the minimum M necessary for achieving optimality in the length of the longest routing path. The longest routing path resulted from a labeling is an important indicator of the performance of any algorithm that runs on the network. We prove that there exists a graph with D = Ω(n1/3) such that if M ≤ n/18D - O(√n/D), the longest path is no shorter than D + Θ(D/√M). As a result, for any M-label IRS, if the longest path is to be shorter than D + Θ(D/√M), at least M = Ω(n/D) labels per edge would be necessary.en_HK
dc.format.extent161576 bytes-
dc.format.extent26112 bytes-
dc.format.mimetypeapplication/pdf-
dc.format.mimetypeapplication/msword-
dc.languageengen_HK
dc.publisherI E E E. The Journal's web site is located at http://www.computer.org/tcen_HK
dc.relation.ispartofIEEE Transactions on Computersen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
dc.rights©1999 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.en_HK
dc.titleOn the space requirement of interval routingen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0018-9340&volume=48&issue=7&spage=752&epage=757&date=1999&atitle=On+the+space+requirement+of+interval+routingen_HK
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_HK
dc.identifier.authorityLau, FCM=rp00221en_HK
dc.description.naturepublished_or_final_versionen_HK
dc.identifier.doi10.1109/12.780884en_HK
dc.identifier.scopuseid_2-s2.0-0032592910en_HK
dc.identifier.hkuros47913-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0032592910&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume48en_HK
dc.identifier.issue7en_HK
dc.identifier.spage752en_HK
dc.identifier.epage757en_HK
dc.identifier.isiWOS:000081670400010-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridTse, SSH=7006643113en_HK
dc.identifier.scopusauthoridLau, FCM=7102749723en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats