File Download
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1109/12.780884
- Scopus: eid_2-s2.0-0032592910
- WOS: WOS:000081670400010
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: On the space requirement of interval routing
Title | On the space requirement of interval routing |
---|---|
Authors | |
Issue Date | 1999 |
Publisher | I 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? |
Abstract | Interval 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 Identifier | http://hdl.handle.net/10722/43649 |
ISSN | 2023 Impact Factor: 3.6 2023 SCImago Journal Rankings: 1.307 |
ISI Accession Number ID | |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Tse, SSH | en_HK |
dc.contributor.author | Lau, FCM | en_HK |
dc.date.accessioned | 2007-03-23T04:51:14Z | - |
dc.date.available | 2007-03-23T04:51:14Z | - |
dc.date.issued | 1999 | en_HK |
dc.identifier.citation | Ieee Transactions On Computers, 1999, v. 48 n. 7, p. 752-757 | en_HK |
dc.identifier.issn | 0018-9340 | en_HK |
dc.identifier.uri | http://hdl.handle.net/10722/43649 | - |
dc.description.abstract | Interval 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.extent | 161576 bytes | - |
dc.format.extent | 26112 bytes | - |
dc.format.mimetype | application/pdf | - |
dc.format.mimetype | application/msword | - |
dc.language | eng | en_HK |
dc.publisher | I E E E. The Journal's web site is located at http://www.computer.org/tc | en_HK |
dc.relation.ispartof | IEEE Transactions on Computers | en_HK |
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. | - |
dc.title | On the space requirement of interval routing | en_HK |
dc.type | Article | en_HK |
dc.identifier.openurl | http://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+routing | en_HK |
dc.identifier.email | Lau, FCM:fcmlau@cs.hku.hk | en_HK |
dc.identifier.authority | Lau, FCM=rp00221 | en_HK |
dc.description.nature | published_or_final_version | en_HK |
dc.identifier.doi | 10.1109/12.780884 | en_HK |
dc.identifier.scopus | eid_2-s2.0-0032592910 | en_HK |
dc.identifier.hkuros | 47913 | - |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-0032592910&selection=ref&src=s&origin=recordpage | en_HK |
dc.identifier.volume | 48 | en_HK |
dc.identifier.issue | 7 | en_HK |
dc.identifier.spage | 752 | en_HK |
dc.identifier.epage | 757 | en_HK |
dc.identifier.isi | WOS:000081670400010 | - |
dc.publisher.place | United States | en_HK |
dc.identifier.scopusauthorid | Tse, SSH=7006643113 | en_HK |
dc.identifier.scopusauthorid | Lau, FCM=7102749723 | en_HK |
dc.identifier.issnl | 0018-9340 | - |