arXiv Open Access 2024

NP-Completeness of Neighborhood Balanced Colorings

Saeed Asaeedi

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.CC

Penulis (1)

Saeed Asaeedi

Format Sitasi

APA MLA BibTeX

Asaeedi, S. (2024). NP-Completeness of Neighborhood Balanced Colorings. https://arxiv.org/abs/2407.19793

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2024
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓