Abstract
We study the following generalization of the classical edge coloring problem: Given a weighted graph, find a partition of its edges into matchings (colors), each one of weight equal to the maximum weight of its edges, so that the total weight of the partition is minimized. We present new approximation algorithms for several variants of the problem with respect to the class of the underlying graph. In particular, we deal with variants which either are known to be NP-hard (general and bipartite graphs) or are proven to be NP-hard in this paper (complete graphs with bi-valued edge weights) or their complexity question still remains open (trees).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Afrati, F.N., Aslanidis, T., Bampis, E., Milis, I.: Scheduling in switching networks with set-up delays. Journal of Combinatorial Optimization 9, 49–57 (2005)
Brucker, P., Gladky, A., Hoogeveen, H., Koyalyov, M., Potts, C., Tautenham, T., van de Velde, S.: Scheduling a batching machine. Journal of Scheduling 1, 31–54 (1998)
Chetwynd, A.G., Hilton, A.J.W.: Regular graphs of high degree are 1-factorizable. In: Proceedings of the London Mathematical Society, vol. 50, pp. 193–206 (1985)
Crescenzi, P., Deng, X., Papadimitriou, C.H.: On approximating a scheduling problem. Journal of Combinatorial Optimization 5, 287–297 (2001)
de Werra, D., Demange, M., Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring on planar, bipartite and split graphs: Complexity and improved approximation. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 896–907. Springer, Heidelberg (2004)
de Werra, D., Hoffman, A.J., Mahadev, N.V.R., Peled, U.N.: Restrictions and preassignments in preemptive open shop scheduling. Discrete Applied Mathematics 68, 169–188 (1996)
Demange, M., de Werra, D., Monnot, J., Paschos, V.T.: Weighted node coloring: When stable sets are expensive. In: Kučera, L. (ed.) WG 2002. LNCS, vol. 2573, pp. 114–125. Springer, Heidelberg (2002)
Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring: further complexity and approximability results. Information Processing Letters 97, 98–103 (2006)
Finke, G., Jost, V., Queyranne, M., Sebő, A.: Batch processing with interval graph compatibilities between tasks. Technical report, Cahiers du laboratoire Leibniz (2004), http://www-leibniz.imag.fr/NEWLEIBNIZ/LesCahiers/index.xhtml
Fiorini, S., Wilson, R.J.: Edge-Colourings of Graphs. Pitman, London (1977)
Gopal, I.S., Wong, C.: Minimizing the number of switchings in a SS/TDMA system. IEEE Transactions On Communications 33, 497–501 (1985)
Holyer, I.: The NP-completeness of edge-coloring. SIAM Journal on Computing 10, 718–720 (1981)
Kesselman, A., Kogan, K.: Nonpreemptive scheduling of optical switches. IEEE Transactions on Communications 55, 1212–1219 (2007)
König, D.: Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen 77, 453–465 (1916)
Kubale, M.: Some results concerning the complexity of restricted colorings of graphs. Discrete Applied Mathematics 36, 35–46 (1992)
Lucarelli, G., Milis, I., Paschos, V.T.: On a generalized graph coloring/batch scheduling problem. In: 3rd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), pp. 353–360 (2007)
Micali, S., Vazirani, V.V.: An \({O(\sqrt{|V|}|E|)}\) algorithm for finding maximum matching in general graphs. In: 21st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 17–27 (1980)
Pemmaraju, S.V., Raman, R.: Approximation algorithms for the max-coloring problem. In: 32nd International Colloquium on Automata, Languages and Programming (ICALP), pp. 1064–1075 (2005)
Pemmaraju, S.V., Raman, R., Varadarajan, K.R.: Buffer minimization using max-coloring. In: 15th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 562–571 (2004)
Rendl, F.: On the complexity of decomposing matrices arising in satellite communication. Operations Research Letters 4, 5–8 (1985)
Vizing, V.G.: On an estimate of the chromatic class of a p-graph. Diskret. Analiz. 3, 25–30 (1964)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lucarelli, G., Milis, I., Paschos, V.T. (2009). On the Maximum Edge Coloring Problem. In: Bampis, E., Skutella, M. (eds) Approximation and Online Algorithms. WAOA 2008. Lecture Notes in Computer Science, vol 5426. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-93980-1_22
Download citation
DOI: https://doi.org/10.1007/978-3-540-93980-1_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-93979-5
Online ISBN: 978-3-540-93980-1
eBook Packages: Computer ScienceComputer Science (R0)