Interval routing in some planar networks. (English) Zbl 1044.68007
Summary: In this article, we design optimal or near optimal Interval Routing Schemes (IRS, for short) with small compactness for several classes of plane quadrangulations and triangulations (by optimality or near optimality we mean that messages are routed via shortest or almost shortest paths). We show that the subgraphs of the rectilinear grid bounded by simple circuits allow optimal IRS with at most two circular intervals per edge (2-IRS). We extend this result to all plane quadrangulations in which all inner vertices have degrees\({\geqslant}\)4. Namely, we establish that every such graph has an optimal IRS with at most seven linear intervals per edge (7-LIRS). This leads to a 7-LIRS with the stretch factor 2 for all plane triangulations in which all inner vertices have degrees\({\geqslant}\)6. All routing schemes can be implemented in linear time.
MSC:
| 68M10 | Network design and communication in computer systems |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | Awerbuch, B.; Bar-Noy, A.; Linial, N.; Peleg, D., Improved routing strategies with succinct tables, J. Algorithms, 11, 307-341 (1990) · Zbl 0724.68004 |
| [2] | Bakker, E. M.; van Leeuwen, J.; Tan, R. B., Linear interval routing, Algorithms Rev., 2, 45-61 (1991) |
| [3] | Bandelt, H.-J.; Chepoi, V., Cellular bipartite graphs, European J. Combin., 17, 121-134 (1996) · Zbl 0848.05054 |
| [4] | Bandelt, H.-J.; Chepoi, V., Decomposition and \(l_1\)-embedding of weakly median graphs, European J. Combin., 21, 701-714 (2000) · Zbl 0965.05081 |
| [5] | Chepoi, V., Graphs of some CAT(0) complexes, Adv. Appl. Math., 24, 125-179 (2000) · Zbl 1019.57001 |
| [6] | Das Sharma, D.; Pradhan, D., Submesh allocation in mesh multicomputers using busy-listsa best-fit approach with complete recognition capability, J. Parallel and Distributed Comput., 36, 106-118 (1996) |
| [7] | Deza, M.; Laurent, M., Geometry of Cuts and Metrics (1997), Springer: Springer Berlin · Zbl 0885.52001 |
| [8] | Djoković, D.Ž., Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B, 14, 263-267 (1973) · Zbl 0245.05113 |
| [9] | Eilam, T.; Moran, S.; Zaks, S., The complexity of characterization of networks supporting shortest-path interval routing, (4th Colloq. on Structural Information and Communication Complexity (SIROCCO) (1997), Carleton University Press: Carleton University Press Waterloo, Ontario), 99-111 · Zbl 1061.68009 |
| [10] | M. Flammini, Deadlock-free interval routing schemes, in: 14th Annu. Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Vol. 1200, Springer, Berlin, 1997, pp. 351-362.; M. Flammini, Deadlock-free interval routing schemes, in: 14th Annu. Symp. on Theoretical Aspects of Computer Science (STACS), Lecture Notes in Computer Science, Vol. 1200, Springer, Berlin, 1997, pp. 351-362. · Zbl 1498.68020 |
| [11] | Fraigniaud, P.; Gavoille, C., Interval routing schemes, Algorithmica, 21, 155-182 (1998) · Zbl 0896.68005 |
| [12] | Fraigniaud, P.; Vial, S., One-to-all and all-to-all communications in partial meshes, Parallel Process. Lett., 9, 9-20 (1999) |
| [13] | Frederickson, G. N.; Janardan, R., Designing networks with compact routing tables, Algorithmica, 3, 171-190 (1988) · Zbl 0646.68087 |
| [14] | Frederickson, G. N.; Janardan, R., Efficient message routing in planar networks, SIAM J. Comput., 19, 164-181 (1990) · Zbl 0696.68022 |
| [15] | Gavoille, C., A survey on interval routing, Theoret. Comput. Sci., 245, 217-253 (2000) · Zbl 0946.68002 |
| [16] | C. Gavoille, S. Pérennès, Lower bounds for interval routing on 3-regular networks, in: N. Santoro, P. Spirakis (Eds.), 3rd Internat. Colloq. on Structural Information and Communication Complexity (SIROCCO) Carleton University Press, Waterloo, Ontario, 1996, pp. 88-103.; C. Gavoille, S. Pérennès, Lower bounds for interval routing on 3-regular networks, in: N. Santoro, P. Spirakis (Eds.), 3rd Internat. Colloq. on Structural Information and Communication Complexity (SIROCCO) Carleton University Press, Waterloo, Ontario, 1996, pp. 88-103. |
| [17] | J. van Leeuwen, R.B. Tan, Computer networks with compact routing tables, in: The Book of L, Springer, Berlin, 1986, pp. 298-307.; J. van Leeuwen, R.B. Tan, Computer networks with compact routing tables, in: The Book of L, Springer, Berlin, 1986, pp. 298-307. |
| [18] | van Leeuwen, J.; Tan, R. B., Interval routing, Comput. J., 30, 298-307 (1987) · Zbl 0652.68051 |
| [19] | Millman, R. S.; Parker, G. D., Geometry. A metric approach with models (1991), Springer: Springer Berlin · Zbl 0724.51001 |
| [20] | Narayanan, L.; Nishimura, N., Interval routing on \(k\)-trees, J. Algorithms, 26, 325-369 (1998) · Zbl 0894.68108 |
| [21] | Narayanan, L.; Shende, S., Partial characterizations of networks supporting shortest path interval labelling schemes, Networks, 32, 103-113 (1998) · Zbl 1015.68008 |
| [22] | Peleg, D.; Upfal, E., A trade-off between space and efficiency for routing tables, J. ACM, 36, 510-530 (1989) · Zbl 0900.68262 |
| [23] | Santoro, N.; Khatib, R., Labeling and implicit routing in networks, Comput. J., 30, 298-307 (1987) · Zbl 0652.68051 |
| [24] | S.S.H. Tse, F.C.M. Lau, Some lower-bound results on interval routing in planar graphs, Technical Report TR-97-05, Department of Computer Science, The University of Hong Kong, April 1997.; S.S.H. Tse, F.C.M. Lau, Some lower-bound results on interval routing in planar graphs, Technical Report TR-97-05, Department of Computer Science, The University of Hong Kong, April 1997. |
| [25] | van de Vel, M. L.J., Theory of Convex Structures (1993), North-Holland: North-Holland Amsterdam · Zbl 0785.52001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
