{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,9,13]],"date-time":"2023-09-13T20:21:22Z","timestamp":1694636482154},"reference-count":38,"publisher":"World Scientific Pub Co Pte Ltd","issue":"01n02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. Inter. Net."],"published-print":{"date-parts":[[2009,3]]},"abstract":"<jats:p>The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the (\u2113, k)-routing problem, each node can send at most \u2113 packets and receive at most k packets. Permutation routing is the particular case \u2113 = k = 1. In the r-central routing problem, all nodes at distance at most r from a fixed node v want to send a packet to v.<\/jats:p><jats:p>In this article we study the permutation routing, the r-central routing and the general (\u2113, k)-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the store-and-forward \u0394-port model, and we consider both full and half-duplex networks. We first survey the existing results in the literature about packet routing, with special emphasis on (\u2113, k)-routing on plane grids. Our main contributions are the following:<\/jats:p><jats:p>1. Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids.<\/jats:p><jats:p>2. Tight r-central routing algorithms on triangular and hexagonal grids.<\/jats:p><jats:p>3. Tight (k, k)-routing algorithms on square, triangular and hexagonal grids.<\/jats:p><jats:p>4. Good approximation algorithms (in terms of running time) for (\u2113, k)-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing.<\/jats:p><jats:p>These algorithms are all completely distributed, i.e., can be implemented independently at each node. Finally, we also formulate the (\u2113, k)-routing problem as a WEIGHTED EDGE COLORING problem on bipartite graphs.<\/jats:p>","DOI":"10.1142\/s0219265909002431","type":"journal-article","created":{"date-parts":[[2009,9,1]],"date-time":"2009-09-01T11:33:49Z","timestamp":1251804829000},"page":"27-57","source":"Crossref","is-referenced-by-count":0,"title":["(\u2113, k)-ROUTING ON PLANE GRIDS"],"prefix":"10.1142","volume":"10","author":[{"given":"FLORIAN","family":"HUC","sequence":"first","affiliation":[{"name":"Centre Universitaire d'Informatique, Battelle b\u00e2timent A, route de Drize 7, 1227 Carouge, Geneva, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"IGNASI","family":"SAU","sequence":"additional","affiliation":[{"name":"Mascotte Project, CNRS\/INRIA\/UNSA\/I3S, 2004 route des Lucioles, B.P. 93 F-06902 Sophia-Antipolis Cedex, France"},{"name":"Graph Theory and Combinatorics group, MA4, UPC, Barcelona, Spain"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JANEZ","family":"\u017dEROVNIK","sequence":"additional","affiliation":[{"name":"Institute of Mathematics, Physics and Mechanics (IMFM), Jadranska 19, Ljubljana, Slovenia"},{"name":"FME, University of Ljubljana, A\u0161ker\u010deva 6, Ljubljana, Slovenia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1145\/258128.258201"},{"key":"rf2","first-page":"109","volume":"90","author":"Aspnes J.","journal-title":"Bulletin of the EATCS"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.010"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626406002551"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0037-3"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2005.172"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_76"},{"key":"rf12","first-page":"114","volume":"2573","author":"Demange M.","journal-title":"WG'02 LNCS"},{"key":"rf13","volume-title":"Graph Theory","author":"Diestel R.","year":"2005"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/S1383-7621(03)00025-0"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1016\/j.sysarc.2005.12.003"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)90180-5"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1006\/jpdc.1998.1483"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48224-5_63"},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1142\/S0129626497000279"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00279-6"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpdc.2005.04.004"},{"key":"rf22","first-page":"223","volume":"24","author":"Kaklamanis C.","journal-title":"Theory of Computing Systems"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1007\/s11227-005-0033-5"},{"key":"rf24","first-page":"1840","author":"Kesselman A.","journal-title":"IEEE GLOBECOM"},{"key":"rf25","first-page":"99","volume":"49","author":"Klav\u017ear S.","journal-title":"MATCH Communications in Mathematical and in Computer Chemistry"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01215349"},{"key":"rf31","volume-title":"Introduction to Parallel Algorithms and Architectures: Arrays-Trees-Hypercubes","author":"Leighton T.","year":"1992"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1007\/BF01294128"},{"key":"rf33","doi-asserted-by":"publisher","DOI":"10.1109\/81.995673"},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1016\/0141-9331(93)90056-D"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2002.1036069"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44681-8_92"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1016\/0743-7315(92)90108-Y"},{"key":"rf42","first-page":"37","volume":"19","author":"Robi\u010d B.","journal-title":"Computers and Artificial Intelligence"},{"key":"rf43","first-page":"1318","volume":"44","author":"Sau I.","journal-title":"Physics and Mechanics"},{"key":"rf45","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0052928"},{"key":"rf46","first-page":"269","volume":"8","author":"Sibeyn J.","journal-title":"International Journal of Fundations of Computer Science"},{"key":"rf48","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.0804"},{"key":"rf50","doi-asserted-by":"publisher","DOI":"10.1109\/71.629486"},{"key":"rf52","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1021\/ci00024a002","volume":"35","author":"To\u0161i\u0107 R.","journal-title":"Journal of Chemical Information and Computer Sciences"},{"key":"rf53","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(00)00063-6"},{"key":"rf55","volume-title":"The Geometrical Foundation of Natural Structure: A Source Book of Design","author":"Williams R.","year":"1979"}],"container-title":["Journal of Interconnection Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0219265909002431","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T07:21:24Z","timestamp":1633850484000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0219265909002431"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,3]]},"references-count":38,"journal-issue":{"issue":"01n02","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,3]]}},"alternative-id":["10.1142\/S0219265909002431"],"URL":"https:\/\/doi.org\/10.1142\/s0219265909002431","relation":{},"ISSN":["0219-2659","1793-6713"],"issn-type":[{"value":"0219-2659","type":"print"},{"value":"1793-6713","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,3]]}}}