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 edges atoms rules smodels dlv ASSAT
(chaff)
p100e570 570 601 2610 n 0.99 0.72 0.38
p300e1760 1760 1801 7980 n 1.62 5.25 0.93
p600e3554 3554 3601 16062 n 2.61 20.43 1.78
p1000e5950 5950 6001 26850 n 4.11 55.03 2.89
p3000e13525 13525 18001 80868 n 11.54 514.31 8.72
p6000e35946 35946 36001 161838 n 22.99 2062.92 17.38
p10000e10000 10000 60001 120000 y 2929.92 --- 33.79
p10000e11000 11000 60001 122997 y 2715.76 --- 32.22
p10000e12000 12000 60001 126000 y 2550.40 --- 30.49
p10000e13000 13000 60001 129000 y 2428.81 --- 28.50
p10000e14000 14000 60001 131997 y 2238.99 --- 27.52
p10000e15000 15000 60001 134997 y 2048.82 --- 27.34
p10000e16000 16000 60001 137997 y 1971.12 --- 25.81
p10000e17000 17000 60001 140994 y 1809.01 --- 25.32
p10000e18000 18000 60001 143997 y 1666.77 --- 25.38
p10000e19000 19000 60001 146994 y 1521.66 --- 119.49
p10000e20000 20000 60001 150000 y 1348.53 --- 120.27
p10000e21000 21000 60001 152997 n 19.69 2201.54 16.49
p10000e22000 22000 60001 155994 ? --- --- ---
p10000e23000 23000 60001 158991 ? --- --- ---
p10000e24000 24000 60001 161988 ? --- --- ---
p10000e25000 25000 60001 164997 ? --- --- ---
p10000e26000 26000 60001 167994 ? --- --- ---
p10000e27000 27000 60001 170988 ? --- --- ---
p10000e28000 28000 60001 173997 ? --- --- ---
p10000e29000 29000 60001 176991 ? --- --- ---
p10000e30000 30000 60001 179985 ? --- --- ---

4-coloring

problem edges atoms rules smodels DLV ASSAT
(chaff)
p100e570 570 801 3880 y 1.09 1860.10 0.49
p300e1760 1760 2401 11840 y 8.94 2.39 1.27
p600e3554 3554 4801 23816 y 37.45 70.76 2.55
p1000e5950 5950 8001 39800 y 109.02 196.69 4.68
p3000e13525 13525 24001 119824 y 1137.33 1733.05 31.47
p6000e35946 35946 48001 239784 y 4714.28 7063.13 309.41
p10000e10000 10000 80001 200000 y 7650.54 --- 70.52
p10000e11000 11000 80001 203996 Y --- 247.75 66.88
p10000e12000 12000 80001 208000 y --- --- 65.60
p10000e13000 13000 80001 212000 y --- --- 64.91
p10000e14000 14000 80001 215996 y --- --- 63.61
p10000e15000 15000 80001 219996 y --- --- 62.80
p10000e16000 16000 80001 223996 y --- --- 61.69
p10000e17000 17000 80001 227992 y --- --- 61.41
p10000e18000 18000 80001 231996 y --- --- 59.76
p10000e19000 19000 80001 235992 y --- --- 57.54
p10000e20000 20000 80001 240000 y --- --- 56.54
p10000e21000 21000 80001 244000 n 29.50 3984.96 24.20
p10000e22000 22000 80001 247992 y --- --- 52.20
p10000e23000 23000 80001 251988 y --- --- 52.34
p10000e24000 24000 80001 255984 y --- --- 50.62
p10000e25000 25000 80001 259996 y --- --- 51.28
p10000e26000 26000 80001 263992 y --- --- 49.71
p10000e27000 27000 80001 267984 y --- --- 47.41
p10000e28000 28000 80001 271996 y --- --- 47.75
p10000e29000 29000 80001 275988 y --- --- 45.58
p10000e30000 30000 80001 279980 y --- --- 44.74

color.lp( Own to Niemela 1999).

A graph pmen means that this graph has m notes and 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.

Yuting Zhao
Last modified: Thursday April 11 2002