Balancing Efficiency and Accuracy: A Comparative Framework of Heuristic and Exact Methods for Graph Coloring in Complex Networks

Authors: Mahaboob Ali

Country: India

Full-text Research PDF File:   View   |   Download

Abstract: An old classic in combinatorial optimisation, the graph colouring problem (GCP) seeks to determine the fewest colours that can be given to vertices in a graph without causing any two neighbouring vertices to have the same colour. Numerous scholars from other disciplines, including mathematics, computer science, and biology, have delved deeply into GCP. Several heuristic algorithms have been suggested as solutions to GCP due to its NP-hardness. Current GCP techniques, on the other hand, are only applicable to sparse networks of high size (up to 10^7 vertices) or to tiny, complex graphs. Solution quality, computational efficiency, scalability, and durability across various graph topologies are the focal points of this paper's comparison approach, which evaluates heuristic and precise techniques for graph coloring—statistical techniques, including heuristics and Integer Linear Programming (ILP). The framework proposes hybrid solutions that combine heuristic limits with accurate refinement to achieve balanced performance in complex network environments.

Keywords: Graph Coloring, independent set, heuristic, exact algorithm, approximate algorithm, sequential algorithm, and parallel algorithms.

Paper Id: 232835

Published On: 2023-06-09

Published In: Volume 11, Issue 3, May-June 2023

Share this