Accéder directement au contenu Accéder directement à la navigation
Communication dans un congrès

On feasible and infeasible search for equitable graph coloring

Abstract : An equitable legal k-coloring of an undirected graph G = (V, E) is a partition of the vertex set V into k disjoint independent sets, such that the cardinalities of any two independent sets differ by at most one (this is called the equity constraint). As a variant of the popular graph coloring problem (GCP), the equitable coloring problem (ECP) involves finding a minimum k for which an equitable legal k-coloring exists. In this paper, we present a study of searching both feasible and infeasible solutions with respect to the equity constraint. The resulting algorithm relies on a mixed search strategy exploring both equitable and inequitable colorings unlike existing algorithms where the search is limited to equitable colorings only. We present experimental results on 73 DIMACS and COLOR benchmark graphs and demonstrate the competitiveness of this search strategy by showing 9 improved best-known results (new upper bounds).
Type de document :
Communication dans un congrès
Liste complète des métadonnées

https://hal.univ-angers.fr/hal-02715117
Contributeur : Okina Université d'Angers <>
Soumis le : mercredi 16 juin 2021 - 15:35:51
Dernière modification le : lundi 21 juin 2021 - 12:21:38
Archivage à long terme le : : vendredi 17 septembre 2021 - 19:21:04

Fichier

Sun2017.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Collections

Citation

Wen Sun, Jin-Kao Hao, Xiangjing Lai, Qinghua Wu. On feasible and infeasible search for equitable graph coloring. Genetic and Evolutionary Computation Conference - GECCO '17, 2017, Berlin, Germany. pp.369-376, ⟨10.1145/3071178.3071267⟩. ⟨hal-02715117⟩

Partager

Métriques

Consultations de la notice

42

Téléchargements de fichiers

14