Abstract
Given a graph G=(V,E) with n vertices, m edges and maximum vertex degree Δ, the load distribution of a coloring . \(\varphi: V \longrightarrow\) red, blue is a pair d ϕ = (r ϕ , b ϕ ), where r ϕ is the number of edges with at least one end-vertex colored red and b ϕ is the number of edges with at least one end-vertex colored blue. Our aim is to find a coloring ϕ such that the (maximum) load, l ϕ := max{r ϕ , b ϕ }, is minimized. The problem has applications in broadcast WDM communication networks (Ageev et al., 2004). After proving that the general problem is NP-hard we give a polynomial time algorithm for optimal colorings of trees and show that the optimal load is at most m/2+\({\it \Delta}\)log2 n. For graphs with genus g>0, we show that a coloring with load OPT(1 + o(1)) can be computed in O(n+g)-time, if the maximum degree satisfies \({\it \Delta} = o(\frac{m^{2}}{ng})\) and an embedding is given. In the general situation we show that a coloring with load at most \({\frac{3} {4}}m+O({\sqrt{{\it \Delta}m}})\) can be found in deterministic polynomial time using a derandomized version of Azuma’s martingale inequality. This bound describes the “typical” situation: in the random multi-graph model we prove that for almost all graphs, the optimal load is at least \(\frac{3}{4}m - {\sqrt{3mn}}\) . Finally, we generalize our results to k–colorings for k > 2.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ageev, A.A., Fishkin, A.V., Kononov, A.V., Sevastianov, S.V.: Open Block Scheduling in Optical Communication Networks. In: Solis-Oba, R., Jansen, K. (eds.) WAOA 2003. LNCS, vol. 2909, pp. 13–26. Springer, Heidelberg (2004)
Azuma, K.: Weighted sums of certain dependent variables. Tohoku Math. Journal 3, 357–367 (1967)
Berman, P., Karpinski, M.: Approximation Hardness of Bounded Degree MIN-CSP and MIN-BISECTION. Electronic Colloquium on Computational Complexity, Report No. 26 (2001)
Diks, K., Djidjev, H.N., Sýkora, O., Vrt̆o, I.: Edge Separators of Planar and Outerplanar Graphs with Applications. Journal of Algorithms 14, 258–279 (1993)
Djidjev, H.N.: A separator theorem. Comptes Rendus de l’Academie Bulgare des Sciences 34, 643–645 (1981)
Even, G., Naor, J., Rao, S., Schieber, B.: Fast Approximate Graph Partitioning Algorithms. SIAM J. Comput. 28(6), 2187–2214 (1999)
Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(33), 237–267 (1976)
Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM Journal on Applied Mathematics 36, 177–189 (1979)
McDiarmid, C.: Concentration. In: Probabilistic Methods for Algorithmic Discrete Mathematics. Algorithms Combin., vol. 16, pp. 195–248. Springer, Berlin (1998)
Srivastav, A.: Derandomizing Martingale Inequalities (preprint 2005); Srivastav, A., Stangier, P.: On quadratic lattice approximations. In: Ng, K.W., Balasubramanian, N.V., Raghavan, P., Chin, F.Y.L. (eds.) ISAAC 1993. LNCS, vol. 762, pp. 176–184. Springer, Heidelberg (1993)
Sýkora, O., Vrt̆o, I.: Edge Separators for Graphs of Bounded Genus with Applications. In: Proc. of the 17th International Workshop on Graph Theoretic Concepts in Computer Science, pp. 159–168 (1992)
Thomassen, C.: The graph genus problem is NP-complete. Journal of Algorithms 10(4), 568–576 (1989)
West, D.B.: Introduction to Graph Theory. Prentice Hall, Englewood Cliffs (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ahuja, N., Baltz, A., Doerr, B., Přívětivý, A., Srivastav, A. (2006). On the Minimum Load Coloring Problem. In: Erlebach, T., Persinao, G. (eds) Approximation and Online Algorithms. WAOA 2005. Lecture Notes in Computer Science, vol 3879. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11671411_2
Download citation
DOI: https://doi.org/10.1007/11671411_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32207-8
Online ISBN: 978-3-540-32208-5
eBook Packages: Computer ScienceComputer Science (R0)