A Hybrid Welsh-Powell-Tabu Search Approach for Efficient Graph Coloring
Journal of Intelligent Decision Making and Information Science · 08.09.2026 · 3 (11s) · 2372-2386
DOI: 10.17762/jidmis.v3.3233 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Intelligent Decision Making and Information Science, online erschienen am 08.09.2026. Verfasst von Jisha Ann Abraham. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Graph coloring is a well-known NP-hard problem with applications to scheduling, frequency assignment, and resource allocation. Heuristic methods, such as Welsh-Powell, provide fast but suboptimal solutions, whereas metaheuristics, including Tabu Search, improve solution quality at the cost of slower convergence and greater sensitivity to initialization. A Hybrid Welsh-Powell-Tabu Search framework incorporates deterministic vertex ordering and adaptive neighborhood refinement. Starting from a feasible coloring generated by Welsh-Powell, the HWPTS proceeds with the Tabu Search approach with the aim of reducing the chromatic number without cycling. Comparative experiments on benchmark graphs, such as dense Erdos-Rényi, irregular Barabási-Albert, planar grids, DIMACS instances, and complete graphs, reveal that the proposed HWPTS yields lower color counts and much faster convergence than either method alone, without incurring significant runtime overhead. Thus, this hybrid approach is quite effective and scalable, hence a generalizable strategy for the graph coloring problem across various topologies.
Zitieren
APA
Abraham, J. A. (2026). A Hybrid Welsh-Powell-Tabu Search Approach for Efficient Graph Coloring. Journal of Intelligent Decision Making and Information Science, 3(11s), 2372-2386. https://doi.org/10.17762/jidmis.v3.3233
Vancouver
Abraham JA. A Hybrid Welsh-Powell-Tabu Search Approach for Efficient Graph Coloring. Journal of Intelligent Decision Making and Information Science. 2026;3(11s):2372-2386. doi:10.17762/jidmis.v3.3233
BibTeX
@article{Abraham2026,
author = {Abraham, Jisha Ann},
title = {A Hybrid Welsh-Powell-Tabu Search Approach for Efficient Graph Coloring},
journal = {Journal of Intelligent Decision Making and Information Science},
year = {2026},
volume = {3},
number = {11s},
pages = {2372--2386},
doi = {10.17762/jidmis.v3.3233}
}
EUVIMED