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 : lundi 1 juin 2020 - 19:58:39
Dernière modification le : mardi 2 juin 2020 - 04:03:49

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

19