Paper Info
Title
Pre-processing and Linear-Decomposition Algorithm to Solve the k-Colorability Problem
Abstract
We are interested in the graph coloring problem. We studied the effectiveness of some pre-processings that are specific to the k-colorability problem and that promise to reduce the size or the difficulty of the instances. We propose to apply on the reduced graph an exact method based on a linear-decomposition of the graph. We present some experiments performed on literature instances, among which DIMACS library instances.
Year
DOI
Venue
2004
10.1007/978-3-540-24838-5_24
Lecture Notes in Computer Science
Keywords
Field
DocType
graph coloring problem
Edge coloring,Strength of a graph,Discrete mathematics,Line graph,Graph property,Computer science,Graph factorization,Algorithm,Null graph,Butterfly graph,Graph coloring
Conference
Volume
ISSN
Citations 
3059
0302-9743
2
PageRank 
References 
Authors
0.38
11
3
Name
Order
Citations
PageRank
Corinne Lucet1998.51
Florence Mendes251.19
Aziz Moukrim337431.97