Abstract
Let G be a graph in which each vertex v has a positive integer weight b(v) and each edge (v,w) has a nonnegative integer weight b(v,w). A bandwidth consecutive multicoloring, simply called a b-coloring of G, assigns each vertex v a specified number b(v) of consecutive positive integers as colors of v so that, for each edge (v,w), all integers assigned to vertex v differ from all integers assigned to vertex w by more than b(v,w). The maximum integer assigned to vertices is called the span of the coloring. The b-coloring problem asks to find a b-coloring of a given graph G with the minimum span. In the paper, we present four efficient approximation algorithms for the problem, which have theoretical performance guarantees for the computation time, the span of a found b-coloring and the approximation ratio. We also obtain several upper bounds on the minimum span, expressed in terms of the maximum b-degrees, one of which is an extension of Brooks’ theorem on an ordinary coloring.
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
Corman, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press and McGraw Hill, Cambridge, MA (2001)
Fijuljamin, J.: Two genetic algorithms for the bandwidth multicoloring problem. Yugoslav Journal of Operation Research 22(2), 225–246 (2012)
Fredman, M.L., Tarjan, R.E.: Fibonacci heaps and their uses in improved network optimization. J. Assoc. Comput. Mach. 34, 596–615 (1987)
Jensen, T.R., Toft, B.: Graph Coloring Problems. John Wiley & Sons, New York (1995)
Lovász, L.: Three short proofs in graph theory. J. Combinatorial Theory (B) 19, 269–271 (1975)
Malaguti, E., Toth, P.: An evolutionary approach for bandwidth multicoloring problems. European Journal of Operation Research 189, 638–651 (2008)
Marti, R., Gortazar, F., Duarte, A.: Heuristics for the bandwidth colouring problem. Int. J. of Metaheuristics 1(1), 11–29 (2010)
McDiamid, C.: On the span in channel assignment problems: bounds, computing and counting. Discrete Math. 266, 387–397 (2003)
McDiamid, C., Reed, B.: Channel assignment on graphs of bounded treewidth. Discrete Math. 273, 183–192 (2003)
Nishikawa, K., Nishizeki, T., Zhou, X.: Algorithms for bandwidth consecutive multicolorings of graphs. In: Snoeyink, J., Lu, P., Su, K., Wang, L. (eds.) AAIM 2012 and FAW 2012. LNCS, vol. 7285, pp. 117–128. Springer, Heidelberg (2012); also Theoretical Computer Science (to appear)
Pinedo, M.L.: Scheduling: Theory, Algorithms and Systems. Springer Science, New York (2008)
Takamizawa, K., Nishizeki, T., Saito, N.: Linear-time computability of combinatorial problems on series-parallel graphs. J. Assoc. Comput. Mach. 29, 623–641 (1982)
West, D.B.: Introduction to Graph Theory. Prentice-Hall, Englewood Cliffs (1996)
Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theoretical Computer Science 3, 103–128 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Obata, Y., Nishizeki, T. (2014). Approximation Algorithms for Bandwidth Consecutive Multicolorings. In: Chen, J., Hopcroft, J.E., Wang, J. (eds) Frontiers in Algorithmics. FAW 2014. Lecture Notes in Computer Science, vol 8497. Springer, Cham. https://doi.org/10.1007/978-3-319-08016-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-319-08016-1_18
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08015-4
Online ISBN: 978-3-319-08016-1
eBook Packages: Computer ScienceComputer Science (R0)