A simple branching scheme for vertex coloring problems |
| |
Authors: | Stefano Gualandi Federico Malucelli |
| |
Institution: | 1. Università di Pavia, Dipartimento di Matematica, via Ferrata 1, Pavia, Italy;2. Politecnico di Milano, Dipartimento di Elettronica ed Informazione, Piazza L. da Vinci 32, Milano, Italy |
| |
Abstract: | We present a branching scheme for some vertex coloring problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as graph multicoloring, where each vertex requires a multiplicity of colors, graph bandwidth coloring, where the colors assigned to adjacent vertices must differ by at least a given distance, and graph bandwidth multicoloring, which generalizes both the multicoloring and the bandwidth coloring problems. We report some computational evidence of the effectiveness of the new branching scheme. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|