×

Coloring all directed paths in a symmetric tree, with an application to optical networks. (English) Zbl 0996.05055

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 colors needed to color the set of all directed paths in \(T\), so that two paths of the same color never use the same directed arc of \(T\), is equal to the maximum number of different paths that contain the same arc of \(T\). The proof implies a polynomial time algorithm for actually coloring the paths with the minimum number of colors. When only a subset of the directed paths is to be colored, the problem is known to be NP-complete; we describe certain instances of the problem which can be efficiently solved. These results are applied to WDM (wavelength-division multiplexing) routing in all-optical networks. In particular, we solve the all-to-all gossiping problem in optical networks.

MSC:

05C15 Coloring of graphs and hypergraphs
05C05 Trees
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] and ?Efficient routing and scheduling algorithms for optical networks,? Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’94), 1994, pp. 412-423. · Zbl 0874.68018
[2] and ?Improved bounds for all optical routing,? Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’95), 1995, pp. 567-576. · Zbl 0960.68514
[3] and ?Graph problems arising from wavelength-routing in all-optical networks,? Proceedings of 2nd Workshop on Optics and Computer Science (WOCS), Geneve, Switzerland, April 1997.
[4] Bermond, Theoret Comp Sci pp 165– (233)
[5] and Graph Theory and Applications, Elsevier, New York, 1976.
[6] Cheung, IEEE JSAC: (Special Issue on Dense WDM Networks) 8 (1990)
[7] and ?Scheduling of virtual connections in fast networks,? Proc of 4th Workshop on Parallel Systems and Algorithms PASA 1996, 1996, pp. 13-32.
[8] and Flows in Networks, Princeton University Press, Cambridge, MA, 1962.
[9] ?Limited wavelength conversion in all-optical tree networks,? Proceedings of 25th International Colloquium on Automata, Languages, and Programming (ICALP 98), Aalborg, July 1998.
[10] and ?Coloring directed paths in symmetric trees, with an application to optical networks,? Proceedings of 24th International Colloquium on Automata, Languages, and Programming (ICALP 97), P. Degano, R. Gorrieri, A. Marchetti-Spaccamela (editors), LNCS 1256, Springer, Bologna, 1997.
[11] Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980. · Zbl 0541.05054
[12] Golumbic, Combin Theory B 38 pp 8– (1985) · Zbl 0537.05063
[13] Green, IEEE Comp 24 pp 78– (1991) · Zbl 05090300
[14] Fiber-Optic Communication Networks, Prentice-Hall 1992.
[15] Approximation results for wavelength routing in directed trees, in preparation.
[16] and Efficient Wavelength Routing on Directed Fiber Trees, ESA’ 96, Barcelona Springer, LNCS 11, pp. 460-470. · Zbl 1379.68014
[17] Lovasz, J Comb Theory B 13 pp 95– (1972) · Zbl 0241.05107
[18] Optical Computer Architectures, Wiley, New York, 1991.
[19] and ?Efficient access to optical bandwidth,? Proceedings of 36th Annual IEEE Symposium on Foundations of Computer Science (FOCS’95), 1995, pp. 548-557. · Zbl 0938.68522
[20] Monma, J Comb Theory B 41 pp 141– (1986) · Zbl 0595.05062
[21] Ramaswami, IEEE Communi Magazine 31 pp 78– (1993)
[22] and ?Efficient routing in all-optical Networks,? Proceedings of the 26th Annual ACM Symposium on Theory of Computing (STOC’94), 1994, pp. 134-143. · Zbl 1345.90038
[23] Combinatorial Mathematics, The Carus Mathematical Monographs (number 14), The Mathematical Association of America, 1973.
[24] Vetter, IEEE Comput 26 pp 8– (1993) · Zbl 05087630
[25] and ?Ring routing and wavelength Translation.? Proceedings of 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’98). · Zbl 0942.68142
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.