×

A refined analysis of online path coloring in trees. (English) Zbl 1484.68338

Jansen, Klaus (ed.) et al., Approximation and online algorithms. 14th international workshop, WAOA 2016, Aarhus, Denmark, August 25–26, 2016. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10138, 142-154 (2017).
Summary: Our results are on the online version of path coloring in trees where each request is a path to be colored online, and two paths that share an edge must get different colors. For each \(T\), we come up with a hierarchical partitioning of its edges with a minimum number of parts, denoted by \(h(T)\), and design an \(O(h(T))\)-competitive online algorithm. We then use the lower bound technique of Y. Bartal and S. Leonardi [Theor. Comput. Sci. 221, No. 1–2, 19–39 (1999; Zbl 0933.68005)] along with a structural property of the hierarchical partitioning, to show a lower bound of \(\varOmega (h(T)/\log (4h(T)))\) for each tree \(T\) on the competitive ratio of any deterministic online algorithm for the problem. This gives us an insight into online coloring of paths on each tree \(T\), whereas the current tight lower bound results are known only for special trees like paths and complete binary trees.
For the entire collection see [Zbl 1355.68016].

MSC:

68W27 Online algorithms; streaming algorithms
05C15 Coloring of graphs and hypergraphs
05C85 Graph algorithms (graph-theoretic aspects)
68R10 Graph theory (including graph drawing) in computer science

Citations:

Zbl 0933.68005
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bartal, Y., Leonardi, S.: On-line routing in all-optical networks. Theor. Comput. Sci. 221(1–2), 19–39 (1999) · Zbl 0933.68005 · doi:10.1016/S0304-3975(99)00025-0
[2] Erlebach, T., Jansen, K., Elvezia, C.: The complexity of path coloring and call scheduling. Theoret. Comput. Sci. 255, 2001 (2000)
[3] Gavril, F.: Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph. SIAM J. Comput. 1(2), 180–187 (1972) · Zbl 0227.05116 · doi:10.1137/0201013
[4] Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theor. Ser. B 16(1), 47–56 (1974) · Zbl 0266.05101 · doi:10.1016/0095-8956(74)90094-X
[5] Gavril, F.: A recognition algorithm for the intersection graphs of paths in trees. Discrete Math. 23(3), 211–227 (1978) · Zbl 0398.05060 · doi:10.1016/0012-365X(78)90003-1
[6] Golumbic, M.C., Jamison, R.E.: Edge and vertex intersection of paths in a tree. Discrete Math. 55(2), 151–159 (1985) · Zbl 0568.05023 · doi:10.1016/0012-365X(85)90043-3
[7] Golumbic, M.C., Jamison, R.E.: The edge intersection graphs of paths in a tree. J. Comb. Theo. Ser. B 38(1), 8–22 (1985) · Zbl 0537.05063 · doi:10.1016/0095-8956(85)90088-7
[8] Kaklamanis, C., Persiano, P.: Efficient wavelength routing on directed fiber trees. In: Diaz, J., Serna, M. (eds.) ESA 1996. LNCS, vol. 1136, pp. 460–470. Springer, Heidelberg (1996). doi: 10.1007/3-540-61680-2_75 · Zbl 1379.68014 · doi:10.1007/3-540-61680-2_75
[9] Kierstead, H.A., Trotter, W.T.: An extremal problem in recursive combinatorics. Congressus Numerantium 33(143–153), 98 (1981) · Zbl 0489.05001
[10] Kumar, V., Schwabe, E.J.: Improved access to optical bandwidth in trees. In Proceedings of SODA 1997, pp. 437–444 (1997) · Zbl 1321.68388
[11] Mihail, M., Kaklamanis, C., Rao, S.: Efficient access to optical bandwidth. In: Proceedings of the 36th Annual Symposium on Foundations of Computer Science, FOCS 1995, p. 548. IEEE Computer Society, Washington, DC (1995) · Zbl 0938.68522
[12] Narayanaswamy, N.S., Subhash, R.: Babu. A note on first-fit coloring of interval graphs. Order 25(1), 49–53 (2008) · Zbl 1149.05044 · doi:10.1007/s11083-008-9076-6
[13] Pemmaraju, S.V., Raman, R., Varadarajan, K.R.: Buffer minimization using max-coloring. In: Ian Munro, J. (ed.) SODA, pp. 562–571. SIAM (2004) · Zbl 1318.68129
[14] Raghavan, P., Upfal, E.: Efficient routing in all-optical networks. In: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing, STOC 1994, pp. 134–143. ACM, New York (1994) · Zbl 1345.90038 · doi:10.1145/195058.195119
[15] Takai, H., Kanatani, T., Matsubayashi, A.: Path coloring on binary caterpillars. IEICE Trans. 89–D(6), 1906–1913 (2006) · doi:10.1093/ietisy/e89-d.6.1906
[16] Tarjan, R.E.: Decomposition by clique separators. Discrete Math. 55(2), 221–232 (1985) · Zbl 0572.05039 · doi:10.1016/0012-365X(85)90051-2
[17] West, D.B.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River, NJ (2000)
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.