×

Colouring paths in directed symmetric trees with applications to WDM routing. (English) Zbl 1401.68245

Degano, Pierpaolo (ed.) et al., Automata, languages and programming. 24th international colloquium, ICALP ’97, Bologna, Italy, July 7–11, 1997. Proceedings. Berlin: Springer-Verlag (ISBN 978-3-540-63165-1/pbk; 978-3-540-69194-5/ebook). Lecture Notes in Computer Science 1256, 505-515 (1997).
Summary: Let \(T\) be a symmetric directed tree, i.e., an undirected tree with each edge viewed as two opposite arcs. We prove that the minimum number of colours needed to colour the set of all directed paths in \(T\), so that no two paths of the same colour use the same arc of \(T\), is equal to the maximum number of paths passing through an arc of \(T\). This result is applied to solve the all-to-all communication problem in wavelength-division-multiplexing (WDM) routing in all-optical networks, that is, we give an efficient algorithm to optimally assign wavelengths to the all the paths of a tree network. It is known that the problem of colouring a general subset of all possible paths in a symmetric directed tree is an NP-hard problem. We study conditions for a given set 5 of paths be coloured efficiently with the minimum possible number of colours/wavelengths.
For the entire collection see [Zbl 1369.68020].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
90B18 Communication networks in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 1.A. Aggarwal, A. Bar-Noy, D. Coppersmith, R. Ramaswami, B. Schieber, M. Sudan. “Efficient Routing and Scheduling Algorithms for Optical Networks”, in \(Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94)\), (1994), 412-423. · Zbl 0874.68018
[2] 2.Y. Aumann and Y. Rabani. “Improved Bounds for All Optical Routing”, \(Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'95)\), (1995), 567-576. · Zbl 0960.68514
[3] 3.B. Awerbuch, Y. Azar, A. Fiat, S. Leonardi, and A. Rosen, “On-Line Competitive Algorithms for Call Admission in Optical Networks”, \(Proceedings of ES A '96\), LNCS 1136, (1996), 431-444. · Zbl 1379.68358
[4] 4.R. A. Barry and P. A. Humblet, “On the Number of Wavelengths and Switches in All-Optical Networks”, in \(IEEE Transactions on Communications\), (1993).
[5] 5.B. Beauquier. “All-to-All Communication for some Wavelength-Routing All-Optical Networks”, \(Manuscript\), (1996). · Zbl 0940.90018
[6] 6.B. Beauquier, J-C. Bermond, L. Gargano, P. Hell, S. Perennes, and U. Vaccaro, “Graph Problems arising from Wavelength-Routing in All-Optical Networks”, \(2nd Workshop on Optics and Computer Science (WOCS)\), April 1997, Geneva, CH.
[7] 7.J-C. Bermond, L. Gargano, S. Perennes, A. Rescigno and U. Vaccaro. “Efficient Collective Communications in Optical Networks”, \(Proc. 23nd ICALP'96, Paderborn, Germany\), (1996). · Zbl 1045.90502
[8] 8.D. P. Bertsekas, and J. N. Tsitsiklis, \(Parallel and Distributed Computation: Numerical Methods\), Prentice-Hall, Englewood Cliffs, NJ, 1989.
[9] 9.J.A. Bondy and U.S.R. Murty, “Graph Theory and Applications”, American Elsevier, N.Y. 1976. · Zbl 1226.05083
[10] 10.N.K. Cheung, K. Nosu and G. Winzer. \(IEEE JSAC\): Special Issue on Dense WDM Networks, vol. 8 (1990).
[11] 11.J. J. Dongarra and D. W. Walker, “Software Libraries for Linear Algebra Computation on High Performances Computers”, \(SIAM Review\), vol. 37, (1995), 151-180. · Zbl 0874.65014
[12] 12.T. Erlebach and K. Jansen. “Scheduling of Virtual Connections in Fast Networks”, \(Proc. of 4th Workshop on Parallel Systems and Algorithms PASA '96\), (1996), 13-32.
[13] 13.G. Fox, M. Johnsson, G. Lyzenga, S. Otto, J. Salmon, and D. Walker, \(Solving Problems on Concurrent Processors, Volume I\), Prentice Hall, Englewood Cliffs, NJ, 1988.
[14] 14.M. C. Golumbic, “Algorithmic Graph Theory and Perfect Graphs”, Academic Press, N.Y. 1980. · Zbl 0541.05054
[15] 15.M. C. Golumbic and R. E. Jamison, The edge intersection grpahs of paths in a tree, J. Combinatorial Theory B 38 (1985) 8-22. · Zbl 0537.05063
[16] 16.P. E. Green. “The Future of Fiber-Optic Computer Networks”, \(IEEE Computer\), vol. 24, (1991), 78-87.
[17] 17.P. E. Green. \(Fiber-Optic Communication Networks\), Prentice-Hall, 1992.
[18] 18.C. Kaklamanis and P. Persiano, “Efficient Wavelength Routing on Directed Fiber Trees”, \(Proc. ESA'96\), Springer Verlag, LNCS 1136, (1996), 460-470. · Zbl 1379.68014
[19] 19.C. Kaklamanis and P. Persiano. “Constrained Bipartite Edge Coloring with Applications to Wavelength Routing”, \(Manuscript\) (1996). · Zbl 1379.68014
[20] 20.S. M. Hedetniemi, S. T. Hedetniemi, and A. Liestman, “A Survey of Gossiping and Broadcasting in Communication Networks”, \(NETWORKS\), 18 (1988), 129-134. · Zbl 0649.90047
[21] 21.J. Hromkovič, R. Klasing, B. Monien, and R. Peine, “Dissemination of Information in Interconnection Networks (Broadcasting and Gossiping)”, in: Ding-Zhu Du and D. Frank Hsu (Eds.) \(Combinatorial Network Theory\), Kluwer Academic Publishers, 1995, pp. 125-212. · Zbl 0840.68088
[22] 22.A. D. McAulay. \(Optical Computer Architectures\), John Wiley, 1991.
[23] 23.M. Mihail, C. Kaklamanis, S. Rao, “Efficient Access to Optical Bandwidth”, \(Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS'95)\), (1995), 548-557. · Zbl 0938.68522
[24] 24.A. Pelc, “Fault Tolerant Broadcasting and Gossiping in Communication Networks”, \(NETWORKS\), to appear. · Zbl 0865.90058
[25] 25.R. Ramaswami, “Multi-Wavelength Lightwave Networks for Computer Communication”, \(IEEE Communication Magazine\), vol. 31, (1993), 78-88.
[26] 26.Y. Rabani. “Path Coloring on the Meshes”, \(Proc. of FOCS '96\).
[27] 27.P. Raghavan and E. Upfal. “Efficient Routing in All-Optical Networks”, \(Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC'94)\), (1994), 134-143. · Zbl 1345.90038
[28] 28.L. Mirsky, Transversal Theory, Academic Press, New York, London, 1971.
[29] 29.R. J. Vetter and D. H. C. Du. “Distributed Computing with High-Speed Optical Networks”, \(IEEE Computer\), vol. 26, (1993), 8-18.
[30] 30.O. Wolfson and A. Segall, “The Communication Complexity of Atomic Commitment and Gossiping”, \(SIAM J. on Computing\), 20 (1991), 423-450. · Zbl 0733.68008
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.