Graph Coloring Domain

More details about this benchmark can be found in the web page: BENCHMARK PROBLEMS FOR ANSWER SET PROGRAMMING SYSTEMS.

3-coloring

problem atoms rules colorable
?
Smodels DLV ASSAT
(mchaff)
p100e570 601 2610 n 1.16 1.53 1.21
p300e1760 1801 7980 n 1.8 6 1.72
p600e3554 3601 16062 n 2.88 20.57 2.56
p1000e5950 6001 26850 n 4.37 54.42 3.45
p3000e13525 18001 80868 n 12.12 512.05 8.69
p6000e35946 36001 161838 n 24.15 2084.58 16.71
p10000e10000 60001 120000 y 2949.31 --- 28.98
p10000e11000 60001 122997 y 2730.38 --- 28.06
p10000e12000 60001 126000 y 2555.93 --- 26.47
p10000e13000 60001 129000 y 2428.49 --- 25.64
p10000e14000 60001 131997 y 2243.74 --- 25.08
p10000e15000 60001 134997 y 2057.88 --- 24.28
p10000e16000 60001 137997 y 1974.6 --- 23.34
p10000e17000 60001 140994 y 1813.68 --- 23.26
p10000e18000 60001 143997 y 1670.77 --- 23.11
p10000e19000 60001 146994 y 1527.13 --- 39.95
p10000e20000 60001 150000 y 1349.05 --- 114.07
p10000e21000 60001 152997 n 20.65 2191.69 15.88
p10000e22000 60001 155994 ? --- --- ---
p10000e23000 60001 158991 ? --- --- ---
p10000e24000 60001 161988 ? --- --- ---
p10000e25000 60001 164997 ? --- --- ---
p10000e26000 60001 167994 ? --- --- ---
p10000e27000 60001 170988 ? --- --- ---
p10000e28000 60001 173997 ? --- --- ---
p10000e29000 60001 176991 ? --- --- ---
p10000e30000 60001 179985 ? --- --- ---




4-coloring

problem atoms rules colorable
?
Smodels DLV ASSAT
(mchaff)
p100e570 801 3880 y 1.89 1919.61 1.35
p300e1760 2401 11840 y 9.85 --- 2.05
p600e3554 4801 23816 y 38.49 72.46 3.08
p1000e5950 8001 39800 y 109.88 204.18 4.67
p3000e13525 24001 119824 y 1141.99 1795.34 26.69
p6000e35946 48001 239784 y 4722.56 --- 144.06
p10000e10000 80001 200000 y --- --- 58.98
p10000e11000 80001 203996 y --- --- 58.09
p10000e12000 80001 208000 y --- --- 57.14
p10000e13000 80001 212000 y --- --- 55.88
p10000e14000 80001 215996 y --- --- 55.52
p10000e15000 80001 219996 y --- --- 54.42
p10000e16000 80001 223996 y --- --- 54.64
p10000e17000 80001 227992 y --- --- 52.30
p10000e18000 80001 231996 y --- --- 51.85
p10000e19000 80001 235992 y --- --- 50.49
p10000e20000 80001 240000 y --- --- 49.60
p10000e21000 80001 244000 n 31.12 3975.25 22.70
p10000e22000 80001 247992 y --- --- 49.33
p10000e23000 80001 251988 y --- --- 46.36
p10000e24000 80001 255984 y --- --- 45.66
p10000e25000 80001 259996 y --- --- 44.03
p10000e26000 80001 263992 y --- --- 43.39
p10000e27000 80001 267984 y --- --- 43.38
p10000e28000 80001 271996 y --- --- 41.55
p10000e29000 80001 275988 y --- --- 41.01
p10000e30000 80001 279980 y --- --- 41.21


A graph pmen means that this graph has m vertices n edges. In particular, p100e570, p300e1760, p600e3554, p1000e5950, p3000e13525, p6000e35946 are the same as p100, p300, p600, p1000, p3000, and p6000 repectively, which appeared in references about Smodels. The graphs with 10000 atoms were generalized randomly.

color.lp( Own to Niemela 1999).


Yuting Zhao
Last modified: Saturday January 3 2003