Abstract
The graph coloring problem (GCP) is one of the most important combinatorial optimization problems that has many practical applications. DSATUR and RLF are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. In this paper, we propose a subgraph degree updating method to improve this issue. Experimental results show that the proposed method is faster than the conventional method and LazyRLF, especially for graphs with higher edge density.
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
Notes
- 1.
In this paper, we consider a DSATUR based heuristic algorithm rather than a DSATUR based branch and bound algorithm shown in [6].
- 2.
- 3.
- 4.
The implementation of the random vertex selection process in the vertex tie-break selection is different for each solution method. Although the accuracy of the solutions is slightly different, the accuracy is comparable with the average.
References
Adegbindin, M., Hertz, A., Bellaïche, M.: A new efficient RLF-like algorithm for the vertex coloring problem. Yugoslav J. Oper. Res. 26(4), 441–456 (2016)
Balabhaskar, B., Sergiy, B.: Graph domination, coloring and cliques in telecommunications. In: Handbook of Optimization in Telecommunications, pp. 865–890. Springer (2006)
Brélaz, D.: New methods to color the vertices of a graph. Commun. ACM 22, 251–256 (1979)
Chaitin,G.J.: Register allocation and spilling via graph coloring. In: Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction, SIGPLAN 1982, pp. 98–105 (1982)
Chiarandini, M., Galbiati, G., Gualandi, S.: Efficiency issues in the RLF heuristic for graph coloring. In: Proceedings of the 9th Metaheuristics International Conference, MIC 2011, pp. 461–469 (2011)
Dimitris, T., Eirini, L., Nikos, P., Lazaros, M.: A graph-coloring secondary resource allocation for D2Dcommunications in LTE networks. In: 2012 IEEE 17th International Workshop on Computer Aided Modeling and Design of Communication Links and Networks (CAMAD), pp. 56–60. IEEE (2012)
Hale, W.K.: Frequency assignment: theory and applications. Proc. IEEE 68(12), 1497–1514 (1980)
Leighton, F.T.: A graph coloring algorithm for large scheduling problems. J. Res. Nat. Bur. Stand. 84(6), 489–506 (1979)
Acknowledgement
This work was supported by JSPS KAKENHI Grant Numbers JP19K12166, JP17K00006.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Kanahara, K., Katayama, K., Miyake, T., Tomita, E. (2021). Speeding-Up of Construction Algorithms for the Graph Coloring Problem. In: Barolli, L., Takizawa, M., Enokido, T., Chen, HC., Matsuo, K. (eds) Advances on Broad-Band Wireless Computing, Communication and Applications. BWCCA 2020. Lecture Notes in Networks and Systems, vol 159. Springer, Cham. https://doi.org/10.1007/978-3-030-61108-8_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-61108-8_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-61107-1
Online ISBN: 978-3-030-61108-8
eBook Packages: EngineeringEngineering (R0)