Path multicoloring with fewer colors in spiders and caterpillars. (English) Zbl 1130.68082
Summary: We study a recently introduced path coloring problem with applications to wavelength assignment in all-optical networks with multiple fibers. In contrast to classical path coloring, it is, in this setting, possible to assign a color more than once to paths that pass through the same edge; the number of allowed repetitions per edge is given and the goal is to minimize the number of colors used. We present algorithms and hardness results for tree topologies of special interest. Our algorithms achieve approximation ratio of 2 in spiders and 3 in caterpillars, whereas the best algorithm for trees so far, achieves an approximation ratio of 4. We also study the directed version of the problem and show that it admits a 3-approximation algorithm in caterpillars, while it can be solved exactly in spiders.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C15 | Coloring of graphs and hypergraphs |
| 90B18 | Communication networks in operations research |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
path coloring; multifiber all-optical networks; approximation algorithms; spiders; caterpillarsReferences:
| [1] | Andrews, M., Zhang, L.: Bounds on fiber minimization in optical networks. In: Proc. INFOCOM, 2005. |
| [2] | Andrews, M., Zhang, L.: Complexity of wavelength assignment in optical network optimization. In: Proc. INFOCOM, 2006. |
| [3] | Andrews, M., Zhang, L.: Wavelength assignment in optical networks with fixed fiber capacity. In: Proc. Automata, Languages and Programming, 31th Int. Colloquium, ICALP 2004, LNCS 3142, pp. 134–145, 2004. · Zbl 1098.68008 |
| [4] | Chekuri, C., Mydlarz, M., Shepherd, F. B.: Multicommodity demand flow in a tree. In: Proc. Automata, Languages and Programming, 30th Int. Colloquium, ICALP 2003, pp. 410–425, 2003. · Zbl 1060.90511 |
| [5] | Cole R., Ost K. and Schirra S. (2001). Edge-coloring bipartite multigraphs in O(Elog D) time. Combinatorica 21(1): 5–12 · Zbl 1107.05305 · doi:10.1007/s004930170002 |
| [6] | Erlebach T. and Jansen K. (2001). The complexity of path coloring and call scheduling. Theor. Comput. Sci. 255(1–2): 33–50 · Zbl 0974.68021 · doi:10.1016/S0304-3975(99)00152-8 |
| [7] | Erlebach T., Jansen K., Kaklamanis C., Mihail M. and Persiano P. (1999). Optimal wavelength routing on directed fiber trees. Theor. Comput. Sci. 221: 119–137. Special issue of ICALP’97 · Zbl 0933.68155 · doi:10.1016/S0304-3975(99)00029-8 |
| [8] | Erlebach, T., Pagourtzis, A., Potika, K., Stefanakos, S.: Resource allocation problems in multifiber WDM tree networks. In: Proc. 29th Workshop on Graph Theoretic Concepts in Computer Science, LNCS, vol. 2880, pp. 218–229, 2003. · Zbl 1255.90028 |
| [9] | Ferreira A., Perennes S., Richa A. W., Rivano H. and Moses N. S. (2003). Models, complexity and algorithms for the design of multifiber WDM networks. Telecommunication Systems 24(2–4): 123–138 · doi:10.1023/A:1026158611840 |
| [10] | Golumbic M. and Jamison R. (1985). Edge intersection graphs of paths in a tree. J. Combin. Theory B 38(1): 8–22 · Zbl 0537.05063 · doi:10.1016/0095-8956(85)90088-7 |
| [11] | Holyer I. (1981). The np-completeness of some edge-partition problems. SIAM J. Comput. 10(4): 713–717 · Zbl 0468.68069 · doi:10.1137/0210054 |
| [12] | Li, G., Simha, R.: On the wavelength assignment problem in multifiber optical tree networks. In: terabit optical networking: architecture, control, and management issues. Proc. SPIE, vol. 4213, pp. 84–91, 2000. |
| [13] | Li G. and Simha R. (2001). On the wavelength assignment problem in multifiber WDM star and ring networks. IEEE/ACM Trans. Network. 9(1): 60–68 · doi:10.1109/90.909024 |
| [14] | Margara, L., Simon, J.: Wavelength assignment problem on all-optical networks with k-fibres per link. In: Proc. Automata, Languages and Programming, 27th Int. Colloquium, ICALP 2000, pp. 768–779, 2000. · Zbl 0973.90502 |
| [15] | Nishizeki T. and Kashiwagi K. (1990). On the 1.1 edge-coloring of multigraphs. SIAM J. Disc. Math. 3(3): 391–410 · Zbl 0702.05036 · doi:10.1137/0403035 |
| [16] | Nomikos, C., Pagourtzis, A., Potika, K., Zachos, S.: Fiber cost reduction and wavelength minimization in multifiber WDM networks. In: NETWORKING, pp. 150–161, 2004. · Zbl 1101.68347 |
| [17] | Nomikos C., Pagourtzis A., Potika K. and Zachos S. (2006). Routing and wavelength assignment in multifiber wdm networks with nonuniform fiber cost. Comput. Network. 50(1): 1–14 · Zbl 1101.68347 · doi:10.1016/j.comnet.2004.11.028 |
| [18] | Nomikos C., Pagourtzis A. and Zachos S. (2001). Routing and path multicoloring. Inf. Process. Lett. 80(5): 249–256 · Zbl 1003.68005 · doi:10.1016/S0020-0190(01)00167-3 |
| [19] | Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: Proc. 26th Annual ACM STOC, pp. 134–143, ACM Press 1994. · Zbl 1345.90038 |
| [20] | Vizing V. (1964). On an estimate of the chromatic class of a p-graph (in Russian). Diskret. Analiz. 3: 23–30 |
| [21] | Winkler, P., Zhang, L.: Wavelength assignment and generalized interval graph coloring. In: Proc. 14th Annual ACM-SIAM SODA, pp. 830–831, Baltimore, MD, 2003. · Zbl 1092.68635 |
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.
