File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Mesh permutation routing with locality

TitleMesh permutation routing with locality
Authors
KeywordsK-K Routing
Mesh-Connected Computers
Mimd
Parallel Algorithms
Permutation Routing
Routing With Locality
Issue Date1992
PublisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/ipl
Citation
Information Processing Letters, 1992, v. 43 n. 2, p. 101-105 How to Cite?
AbstractGiven the permutation routing problem on mesh-connected arrays with a known maximum distance, d, between any source- destination pair, we show how sorting and the greedy algorithm can be combined to yield a deterministic, asymptotically optimal algorithm for solving the problem. This simple algorithm runs in d+O(d/f(d)) time and requires an O(f;(d)) buffer size (or O(d) time and constant buffer size if we choose f(d) to be a constant). It also gives efficient solutions to the k-k routing problem with locality.
Persistent Identifierhttp://hdl.handle.net/10722/152198
ISSN
2023 Impact Factor: 0.7
2023 SCImago Journal Rankings: 0.404
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorCheung, Sen_US
dc.contributor.authorLau, FCMen_US
dc.date.accessioned2012-06-26T06:36:27Z-
dc.date.available2012-06-26T06:36:27Z-
dc.date.issued1992en_US
dc.identifier.citationInformation Processing Letters, 1992, v. 43 n. 2, p. 101-105en_US
dc.identifier.issn0020-0190en_US
dc.identifier.urihttp://hdl.handle.net/10722/152198-
dc.description.abstractGiven the permutation routing problem on mesh-connected arrays with a known maximum distance, d, between any source- destination pair, we show how sorting and the greedy algorithm can be combined to yield a deterministic, asymptotically optimal algorithm for solving the problem. This simple algorithm runs in d+O(d/f(d)) time and requires an O(f;(d)) buffer size (or O(d) time and constant buffer size if we choose f(d) to be a constant). It also gives efficient solutions to the k-k routing problem with locality.en_US
dc.languageengen_US
dc.publisherElsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/iplen_US
dc.relation.ispartofInformation Processing Lettersen_US
dc.subjectK-K Routingen_US
dc.subjectMesh-Connected Computersen_US
dc.subjectMimden_US
dc.subjectParallel Algorithmsen_US
dc.subjectPermutation Routingen_US
dc.subjectRouting With Localityen_US
dc.titleMesh permutation routing with localityen_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.1016/0020-0190(92)90019-Ren_US
dc.identifier.scopuseid_2-s2.0-0011677024en_US
dc.identifier.volume43en_US
dc.identifier.issue2en_US
dc.identifier.spage101en_US
dc.identifier.epage105en_US
dc.identifier.isiWOS:A1992JN00600008-
dc.publisher.placeNetherlandsen_US
dc.identifier.scopusauthoridCheung, S=8059068300en_US
dc.identifier.scopusauthoridLau, FCM=7102749723en_US
dc.identifier.issnl0020-0190-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats