Abstract
We study the weighted vertex coloring problem (WVCP) in binary trees and a restricted class of cactus graphs we called cactus paths. WVCP is a generalization of the vertex coloring problem where a color class of a feasible coloring is assigned a cost equal to the largest weight of a vertex from the color class. The objective is to find a feasible coloring which minimizes the sum of the color costs assigned to each color class. We improve the exact algorithms for solving WVCP on binary trees and propose new and efficient algorithms for WVCP on cycles and cactus paths with maximum degree three. Our work extends the results of Kavitha and Mestre [8]. Our algorithms have a time complexity of \(O(n \log ^2 n)\) for cactus paths and \(O(n^2 \log n)\) for binary trees.
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
Similar content being viewed by others
References
Araujo, J., Nisse, N., Pérennes, S.: Weighted coloring in trees. SIAM J. Discrete Math. 28(4), 2029–2041 (2014)
Benkoczi, R.R.: Cardinality constrained facility location problems in trees. Ph.D. Thesis, Simon Fraser University (2004)
Escoffier, B., Monnot, J., Paschos, V.T.: Weighted coloring: further complexity and approximability results. Inf. Process. Lett. 97(3), 98–103 (2006)
Fritsch, R., Peschke, J., Fritsch, G.: The Four-Color Theorem: History, Topological Foundations, and Idea of Proof. Springer, New York (2012)
Gary, M.R., Johnson, D.S.: Computers and Intractability A Guide to the Theory of np-Completeness. WH Freman and Co, New York (1979)
Guan, D.J., Xuding, Z.: A coloring problem for weighted graphs. Inf. Process. Lett. 61(2), 77–81 (1997)
Halldórsson, M.M., Shachnai, H.: Batch coloring flat graphs and thin. In: Gudmundsson, J. (ed.) SWAT 2008. LNCS, vol. 5124, pp. 198–209. Springer, Heidelberg (2008)
Kavitha, T., Mestre, J.: Max-coloring paths: tight bounds and extensions. J. Comb. Optim. 24(1), 1–14 (2012)
Khan, N., Pal, A., Pal, M.: Edge colouring of cactus graphs. Adv. Model. Optim 11(4), 407–421 (2009)
Kratochvil, J., Tuza, Z.: Algorithmic complexity of list colorings. Discrete Appl. Math. 50(3), 297–302 (1994)
Lewis, R.: A Guide to Graph Colouring, Algorithms and Applications. Springer, Switzerland (2015)
Malaguti, E., Monaci, M., Toth, P.: Models and heuristic algorithms for a weighted vertex coloring problem. J. Heuristics 15(5), 503–526 (2009)
McDiarmid, C., Reed, B.: Channel assignment and weighted coloring. Networks 36(2), 114–117 (2000)
Mishra, A., Banerjee, S., Arbaugh, W.: Weighted coloring based channel assignment for wlans. SIGMOBILE Mob. Comput. Commun. Rev. 9(3), 19–31 (2005)
Pemmaraju, S.V., Raman, R.: Approximation algorithms for the max-coloring problem. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 1064–1075. Springer, Heidelberg (2005)
Prais, M., Ribeiro, C.C.: Reactive GRASP: an application to a matrix decomposition problem in TDMA traffic assignment. INFORMS J. Comput. 12(3), 164–176 (2000)
Ribeiro, C.C., Minoux, M., Penna, M.C.: An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment. Eur. J. Oper. Res. 41(2), 232–239 (1989)
Acknowledgements
Robert Benkoczi’s and Daya Ram Gaur’s research was supported in part by individual NSERC Discovery Grants. Ram Dahal’s research was supported by the PIMS and the School of Graduate Studies, University of Lethbridge. We would like to thank the anonymous reviewers for their insightful comments that help improve the quality of the paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Benkoczi, R., Dahal, R., Gaur, D.R. (2016). Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs. In: Mäkinen, V., Puglisi, S., Salmela, L. (eds) Combinatorial Algorithms. IWOCA 2016. Lecture Notes in Computer Science(), vol 9843. Springer, Cham. https://doi.org/10.1007/978-3-319-44543-4_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-44543-4_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-44542-7
Online ISBN: 978-3-319-44543-4
eBook Packages: Computer ScienceComputer Science (R0)