Abstract
For a connected graph G, an instance I is a set of pairs of vertices and a corresponding routing R is a set of paths specified for all vertex-pairs in I. Let \(\mathfrak {R}_I\) be the collection of all routings with respect to I. The undirected optical index of G with respect to I refers to the minimum integer k to guarantee the existence of a mapping \(\phi :R\rightarrow \{1,2,\ldots ,k\}\), such that \(\phi (P)\ne \phi (P')\) if P and \(P'\) have common edge(s), over all routings \(R\in \mathfrak {R}_I\). A natural lower bound of the undirected optical index is the edge-forwarding index, which is defined to be the minimum of the maximum edge-load over all possible routings. Let w(G, I) and \(\pi (G,I)\) denote the undirected optical index and edge-forwarding index with respect to I, respectively. In this paper, we derive the inequality \(w(T,I_A)<\frac{3}{2}\pi (T,I_A)\) for any tree T, where \(I_A:=\{\{x,y\}:\,x,y\in V(T)\}\) is the all-to-all instance.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data Availability
No data was used for the research described in the article.
References
Alexander SB et al (1993) A precompetitive consortium on wide-band all-optical networks. J Lightw Technol 11(56):714–735
Amar D, Raspaud A, Togni O (2001) All-to-all wavelength-routing in all-optical compound networks. Discrete Math 235:353–363
Beauquier B (1999) All-to-all communication for some wavelength-routed all-optical networks. Networks 33:179–187
Beauquier B, Bermond J-C, Gargano L, Hell P, Pérennes S, Vaccaro U (1997) Graph problems arising from wavelength-routing in all-optical networks. In Proceeding 2nd Workshop on Optics and Computer Science, WOCS’97, Geneve, Switzerland, April
Beauquier B, Pérennes S, Tóth D (1999) All-to-all routing and coloring in weighted trees of rings. In: Proceeding 11th Annual ACM Symposium on Parallel Algorithms and Architectures, SPAA’99, ACM, pp 185–190
Caragiannis I (2009) Wavelength management in WDM rings to maximize the number of connections. SIAM J Discrete Math 23(2):959–978
Cheng CT (2004) Improved approximation algorithms for the demand routing and slotting problem with unit demands on rings. SIAM J Discrete Math 17:384–402
Erlebach T, Jansen K (2001) The complexity of path coloring and call scheduling. Theoret Comput Sci 255:33–50
Erlebach T, Jansen K, Kaklamanis C, Mihail M, Persiano P (1999) Optimal wavelength routing on directed fiber trees. Theoret Comput Sci 221:119–137
Fu H-L, Lo Y-H, Wong WS, Zhang Y (2020) The undirected optical indices of complete \(m\)-ary trees. Discr Appl Math 285:173–181
Gargano L, Hell P, Perennes S (1997) Colouring directed paths in a symmetric tree with applications to WDM routing. In: Proceeding 24th international colloquium on algorithm, languages and programming ICALP’97, vol. 1256, Springer, Berlin, pp. 505–515
Gan H-S, Mokhtar H, Zhou S (2015) Forwarding and optical indices of 4-regular circulant networks. J Discr Algorith 35:27–39
Golumbic MC, Jamison RE (1985) The edge intersection graphs of paths in a tree. J Comb Theory Series B 38(1):8–22
Heydemann MC, Meyer JC, Sotteau D (1989) On forwarding indices of networks. Discrete Appl Math 23(2):103–123
Kosowski A (2009) Forwarding and optical indices of a graph. Discrete Appl Math 157(2):321–329
Kaklamanis C, Persiano P, Erlebach T, Jansen K (1997) Constrained bipartite edge coloring with applications to wavelength routing. In: Proceeding 24th Internation Colloquium on Automata, Languages and Programming ICALP’97, Springer, Berlin, vol. 1256, pp. 493–504
Lampis M (2013) Parameterized maximum path coloring. Theoret Comput Sci 511:42–53
Lo Y-H, Zhang Y, Wong WS, Fu H-L The global packing number for an optical network, [Online]. Available: arXiv:1509.07029
Qian J, Zhang F (2004) Expanding and forwarding parameters of product graphs. Discrete Appl Math 136:63–82
Raghavan P, Upfal E (1994) Efficient routing in all-optical networks, Proceeding 26th Annual ACM symposium on theory of computing STOC’94, pp. 134–143
Solé P (1995) Expanding and forwarding. Discrete Appl Math 58:67–79
Schröder H, Sýkora O, Vrtó I (1997) Optical all-to-all communication for some product graphs. In: Proceedings of the 24th seminar current trends in theory and practice of information, vol. LNCS 1338, pp. 555–562
Shannon CE (1949) A theorem on coloring the lines of a network. J Math Phys 28:148–151
Tarjan RE (1985) Decomposition by clique separators. Discrete Math 55:221–232
Tucker A (1975) Coloring a family of circular arcs. SIAM J Appl Math 29(3):493–502
West DB (2001) Introduction to graph theory, vol 2. Prentice-Hall, Upper Saddle River, NJ
Wilfong G (1996) Minimizing wavelengths in an all-optical ring network. In: Proceeding of international symposium on algorithm and computation, pp. 346–355
Yap HP (1996) Total Colourings of Graphs, vol 1623. Lecture Notes in Math. Springer, Berlin
Acknowledgements
The authors thank the referees for reading the manuscript carefully and providing helpful suggestions that improve the presentation of the paper. This work was supported in part by the National Science and Technology Council of Taiwan (Nos. 112-2115-M-153-004-MY2 and 104-2115-M-009-009) and the Fundamental Research Funds for the Central Universities of China (No. 30920021127).
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Ethical approval
This article does not contain any studies with human participants or animals performed by any of the authors.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Lo, YH., Fu, HL., Zhang, Y. et al. The undirected optical indices of trees. J Comb Optim 49, 22 (2025). https://doi.org/10.1007/s10878-024-01255-2
Accepted:
Published:
DOI: https://doi.org/10.1007/s10878-024-01255-2