An exact DSatur-based algorithm for the Equitable Coloring Problem期刊界 All Journals 搜尽天下杂志传播学术成果专业期刊搜索期刊信息化学术搜索

An exact DSatur-based algorithm for the Equitable Coloring Problem

Affiliation:	1. FCEyN, Universidad de Buenos Aires, Argentina;2. FCEIA, Universidad Nacional de Rosario y CONICET Argentina;1. Instituto de Informática, Universidade Federal de Goiás, Brazil;2. Institut für Optimierung und Operations Research, Universität Ulm, Germany;3. PESC, COPPE, Universidade Federal do Rio de Janeiro, Brazil;4. Inst Mat., COPPE and NCE, Universidade Federal do Rio de Janeiro, Brazil;1. Universidad Nacional de Rosario, Argentina;2. CONICET and Universidad Nacional de Rosario, Argentina

Abstract:	This paper describes an exact algorithm for the Equitable Coloring Problem, based on the well known DSatur algorithm for the classic Coloring Problem with new pruning rules specifically derived from the equity constraint. Computational experiences show that our algorithm is competitive with those known in literature.

Keywords:	equitable coloring DSatur exact algorithm
本文献已被 ScienceDirect 等数据库收录！