File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A Lower Bound for Interval Routing in General Networks

TitleA Lower Bound for Interval Routing in General Networks
Authors
Issue Date1997
PublisherJohn Wiley & Sons, Inc. The Journal's web site is located at http://www.interscience.wiley.com/jpages/0028-3045/
Citation
Networks, 1997, v. 29 n. 1, p. 49-53 How to Cite?
AbstractInterval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings have existed for regular as well as some of the common topologies, but not for arbitrary graphs. In fact, it has already been shown that it is impossible to find optimal labelings for arbitrary graphs. In this paper, we prove a 7D/4 - 1 lower bound for interval routing in arbitrary graphs, where D is the diameter - i.e., the best any interval labeling scheme could do is to produce a longest path having a length of at least 7D/4 - 1. © 1997 John Wiley & Sons, Inc.
Persistent Identifierhttp://hdl.handle.net/10722/152309
ISSN
2015 Impact Factor: 0.943
2015 SCImago Journal Rankings: 1.043
References

 

DC FieldValueLanguage
dc.contributor.authorTse, SSHen_US
dc.contributor.authorLau, FCMen_US
dc.date.accessioned2012-06-26T06:37:05Z-
dc.date.available2012-06-26T06:37:05Z-
dc.date.issued1997en_US
dc.identifier.citationNetworks, 1997, v. 29 n. 1, p. 49-53en_US
dc.identifier.issn0028-3045en_US
dc.identifier.urihttp://hdl.handle.net/10722/152309-
dc.description.abstractInterval routing is a space-efficient routing method for point-to-point communication networks. The method has drawn considerable attention in recent years because of its being incorporated into the design of a commercially available routing chip. The method is based on proper labeling of edges of the graph with intervals. An optimal labeling would result in routing of messages through the shortest paths. Optimal labelings have existed for regular as well as some of the common topologies, but not for arbitrary graphs. In fact, it has already been shown that it is impossible to find optimal labelings for arbitrary graphs. In this paper, we prove a 7D/4 - 1 lower bound for interval routing in arbitrary graphs, where D is the diameter - i.e., the best any interval labeling scheme could do is to produce a longest path having a length of at least 7D/4 - 1. © 1997 John Wiley & Sons, Inc.en_US
dc.languageengen_US
dc.publisherJohn Wiley & Sons, Inc. The Journal's web site is located at http://www.interscience.wiley.com/jpages/0028-3045/en_US
dc.relation.ispartofNetworksen_US
dc.rightsNetworks. Copyright © John Wiley & Sons, Inc.-
dc.titleA Lower Bound for Interval Routing in General Networksen_US
dc.typeArticleen_US
dc.identifier.emailLau, FCM:fcmlau@cs.hku.hken_US
dc.identifier.authorityLau, FCM=rp00221en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1002/(SICI)1097-0037(199701)29:1<49::AID-NET5>3.0.CO;2-C-
dc.identifier.scopuseid_2-s2.0-0346880118en_US
dc.identifier.hkuros29174-
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-0346880118&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume29en_US
dc.identifier.issue1en_US
dc.identifier.spage49en_US
dc.identifier.epage53en_US
dc.publisher.placeUnited Statesen_US
dc.identifier.scopusauthoridTse, SSH=7006643113en_US
dc.identifier.scopusauthoridLau, FCM=7102749723en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats