Abstract
We consider two generalizations of the edge coloring problem in bipartite graphs. The first problem we consider is the weighted bipartite edge coloring problem where we are given an edge-weighted bipartite graph G = (V,E) with weights w:E→[0,1]. The task is to find a proper weighted coloring of the edges with as few colors as possible. An edge coloring of the weighted graph is called a proper weighted coloring if the sum of the weights of the edges incident to a vertex of any color is at most one. We give a polynomial time algorithm for the weighted bipartite edge coloring problem which returns a proper weighted coloring using at most ⌈2.25 n⌉ colors where n is the maximum total weight incident at any vertex. This improves on the previous best bound of Correa and Goemans [5] which returned a coloring using 2.557n + o(n) colors. The second problem we consider is the Balanced Decomposition of Bipartite graphs problem where we are given a bipartite graph G = (V,E) and α 1,...,α k ∈ (0,1) summing to one. The task is to find a partition E 1,..., E k of E such that \(deg_{E_i}(v)\) is close to α i deg E (v) for each 1 ≤ i ≤ k and v ∈ V. We give an alternate proof of the result of Correa and Goemans [5] that there is a decomposition such that \(\lfloor\alpha_i deg_E(v) \rfloor -2 \leq deg_{E_i}(v) \leq \lceil \alpha_i deg_E(v) \rceil +2\) for each v ∈ V and 1 ≤ i ≤ k. Moreover, we show that the additive error can be improved from two to one if only upper bounds or only lower bounds on the degree are present. All our results hold also for bipartite multigraphs, and the decomposition results hold also for general graphs.
Part of this work was performed at Microsoft Research, Redmond, Washington.
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
Beck, J., Fiala, T.: “Integer-Making” Theorems. Discrete Applied Mathematics 3, 1–8 (1981)
Beetem, J., Denneau, M., Weingarten, D.: The GF11 Supercomputer. In: Proceedings of the 12th annual international symposium on Computer architecture, Boston, Massachusetts, United States, June 17-19, pp. 108–115 (1985)
Chung, S.-P., Ross, K.W.: On Nonblocking Multirate Interconnection Networks. SIAM Journal of Computing 20(4), 726–736 (1991)
Clos, C.: A Study of Nonblocking Switching Networks. Bell System Technical Journal 32(2), 406–424 (1953)
Correa, J., Goemans, M.X.: Improved Bounds on Nonblocking 3-Stage Clos Networks. SIAM Journal of Computing 37, 870–894 (2007)
Correa, J.R., Matamala, M.: Some Remarks About Factors of Graphs. Journal of Graph Theory 57, 265–274 (2008)
de Werra, D.: On Some Combinatorial Problems arising in Scheduling. Operations Research Society Journal 8, 165–175 (1970)
Du, D.Z., Gao, B., Hwang, F.K., Kim, J.H.: On Multirate Rearrangeable Clos Networks. SIAM Journal on Computing 28(2), 463–470 (1999)
Hoffman, A.J.: Generalization of a theorem of König. Journal of the Washington Academy of Science 46, 211–212 (1956)
Itoh, A., Takahashi, W., Nagano, H., Kurisaka, M., Iwasaki, S.: Practical Implementation and Packaging Technologies for a Large-Scale ATM Switching System. Journal of Selected Areas in Communications 9, 1280–1288 (1991)
Kano, M., Saito, A.: [a,b]-factors of graphs. Discrete Mathematics 47, 113–116 (1983)
König, D.: Graphok és Alkalmazásuk a Determinánsok és a Halmazok Elméletére. Mathematikai és Termszettudományi értesitö 34, 104–119 (1916)
Lin, G.-H., Du, D.-Z., Hu, X.-D., Xue, G.: On Rearrangeability of Multirate Clos Networks. SIAM Journal on Computing 28(4), 1225–1231 (1999)
Lin, G., Du, D., Wu, W., Yoo, K.: On 3-Rate Rearrangeability of Clos Networks. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 42, 315–333 (1998)
Melen, R., Turner, J.S.: Nonblocking Multirate Networks. SIAM Journal on Computing 18(2), 301–313 (1989)
Ngo, H.Q., Vu, V.H.: Multirate Rearrangeable Clos Networks and a Generalized Edge Coloring Problem on Bipartite Graphs. In: Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, Baltimore, Maryland, January 12-14 (2003)
Slepian, D.: Two Theorems on a Particular Crossbar Switching (unpublished manuscript, 1958)
Vizing, V.G.: On an Estimate of the Chromatic Class of a p-Graph (in Russian). Diskret. Analiz 3, 23–30 (1964)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Feige, U., Singh, M. (2008). Edge Coloring and Decompositions of Weighted Graphs. In: Halperin, D., Mehlhorn, K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87744-8_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-87744-8_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87743-1
Online ISBN: 978-3-540-87744-8
eBook Packages: Computer ScienceComputer Science (R0)