6533b873fe1ef96bd12d59d5
RESEARCH PRODUCT
An exact method for graph coloring
Aziz MoukrimFlorence MendesCorinne Lucetsubject
Discrete mathematics021103 operations research[INFO.INFO-RO] Computer Science [cs]/Operations Research [cs.RO]General Computer Science0211 other engineering and technologies[INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO]0102 computer and information sciences02 engineering and technologyManagement Science and Operations Research01 natural scienceslaw.inventionCombinatoricsEdge coloring010201 computation theory & mathematicslawGraph powerModeling and SimulationLine graphGraph homomorphismGraph coloringFractional coloringGraph factorizationMathematicsList coloring[ INFO.INFO-RO ] Computer Science [cs]/Operations Research [cs.RO]description
International audience; We are interested in the graph coloring problem. We propose an exact method based on a linear-decomposition of the graph. The complexity of this method is exponential according to the linearwidth of the entry graph, but linear according to its number of vertices. We present some experiments performed on literature instances, among which COLOR02 library instances. Our method is useful to solve more quickly than other exact algorithms instances with small linearwidth, such as mug graphs. Moreover, our algorithms are the first to our knowledge to solve the COLOR02 instance 4-Inser_3 with an exact method.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2006-08-01 |