Share This Article:

Cost Edge-Coloring of a Cactus

Abstract Full-Text HTML XML Download Download as PDF (Size:662KB) PP. 119-134
DOI: 10.4236/wjet.2015.33C018    2,756 Downloads   3,053 Views  

ABSTRACT

Let C be a set of colors, and let  be an integer cost assigned to a color c in C. An edge-coloring of a graph  is assigning a color in C to each edge  so that any two edges having end-vertex in common have different colors. The cost  of an edge-coloring f of G is the sum of costs  of colors  assigned to all edges e in G. An edge-coloring f of G is optimal if  is minimum among all edge-colorings of G. A cactus is a connected graph in which every block is either an edge or a cycle. In this paper, we give an algorithm to find an optimal edge-   coloring of a cactus in polynomial time. In our best knowledge, this is the first polynomial-time algorithm to find an optimal edge-coloring of a cactus.

Conflicts of Interest

The authors declare no conflicts of interest.

Cite this paper

Ye, Z. , Li, Y. , Lu, H. and Zhou, X. (2015) Cost Edge-Coloring of a Cactus. World Journal of Engineering and Technology, 3, 119-134. doi: 10.4236/wjet.2015.33C018.

References

[1] West, D.B. (2000) Introduction to Graph Theory. 2nd Edition, Prentice Hall, New Jersey.
[2] Hajiabolhassan, H., Mehrabadi, M.L. and Tusserkani, R. (2000) Minimal Coloring and Strength of Graphs. Discrete Mathematics, 215, 265-270. http://dx.doi.org/10.1016/S0012-365X(99)00319-2
[3] Mitchem, J., Morriss, P. and Schmeichel, E. (1997) On the Cost Chromatic Number of Outerplanar, Planar, and Line Graphs. Discussiones Mathematicae Graph Theory, 17, 229-241. http://dx.doi.org/10.7151/dmgt.1050
[4] Giaro, K. and Kubale, M. (2000) Edge-Chromatic Sum of Trees and Bounded Cyclicity Graphs. Information Process- ing Letters, 75, 65-69. http://dx.doi.org/10.1016/S0020-0190(00)00072-7
[5] Zhou, X. and Nishizeki, T. (2004) Algorithm for the Cost Edge-Coloring of Trees. J. Combinatorial Optimization, 8, 97-108. http://dx.doi.org/10.1023/B:JOCO.0000021940.40066.0c
[6] Coffman, E.G., Garey, M.R., Johnson, D.S. and LaPaugh, A.S. (1985) Scheduling File Transfers. SIAM J. Computing, 14, 744-780. http://dx.doi.org/10.1137/0214054
[7] Krawczyk, H. and Kubale, M. (1985) An Approximation Algorithm for Diagnostic Test Scheduling in Multicomputer Systems. IEEE Trans. Computers, 34, 869-872. http://dx.doi.org/10.1109/TC.1985.1676647
[8] Marx, D. (2009) Complexity Results for Minimum Sum Edge Co-loring. Discrete Applied Mathematics, 157, 1034- 1045. http://dx.doi.org/10.1016/j.dam.2008.04.002
[9] Goldberg, A.V. and Tarjan, R.E. (1987) Solving Minimum Cost Flow Problems by Successive Approximation. Proc. 19th ACM Symposium on the Theory of Computing, 7-18. http://dx.doi.org/10.1145/28395.28397
[10] Goldberg, A.V. and Tar-jan, R.E. (1989) Finding Minimum-Cost Circulations by Canceling Negative Cycles. J. ACM, 36, 873-886. http://dx.doi.org/10.1145/76359.76368

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.