EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Hybrid Welsh-Powell-Tabu Search Approach for Efficient Graph Coloring

Jisha Ann Abraham

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →