2024/07/29 by Saeed Asaeedi, Asaeedi, Saeed · 1 citation
Decision Sciences · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.2407.19793
openalex publication_date 2024/07/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A Neighborhood Balanced Coloring (NBC) of a graph is a red-blue coloring where each vertex has the same number of red and blue neighbors. This work proves that determining if a graph admits an NBC is NP-complete. We present a genetic algorithm to solve this problem, which we implemented and compared against exact and randomized algorithms.