K-Coloring

CLP(FD) code:

coloring.pl (SICStus)

ASP code:

coloring.lp

Results:

Graph K-coloring (`-' denotes no answer in at least 30 minutes of CPU-time).

Instance		3-colorability				4-colorability				5-colorability
Graph	V$\times$E		SModels	CModels	SICStus		SModels	CModels	SICStus		SModels	CModels	SICStus
1-FullIns_5 .pl, .lp	282$\times$3247	N	1.06	0.15	0.1	N	-	0.23	2.9	N	-	107.78	-
4-FullIns_4 .pl, .lp	690$\times$6650	N	0.94	0.29	0.46	N	2.20	0.35	1.98	N	10.02	0.42	-
5-FullIns_4 .pl, .lp	1085$\times$11395	N	1.72	0.47	1.26	N	4.67	0.57	3.58	N	23.79	0.70	-
3-FullIns_5 .pl, .lp	2030$\times$33751	N	5.92	1.23	7.24	N	21.31	1.51	13.69	N	-	1.96	-
4-FullIns_5 .pl, .lp	4146$\times$77305	N	15.11	2.69	33.44	N	69.30	3.37	42.53	N	414.93	4.19	-
3-Insertions_3 .pl, .lp	56$\times$110	N	4.28	4.16	1281.18	Y	0.03	0.04	$<$0.01	Y	0.04	0.04	$<$0.01
4-Insertions_3 .pl, .lp	79$\times$156	N	328.25	1772.14	-	Y	0.05	0.04	$<$0.01	Y	0.06	0.05	$<$0.01
2-Insertions_4 .pl, .lp	149$\times$541	N	1.20	0.15	2.04	?	-	-	-	Y	0.25	0.07	0.01
4-Insertions_4 .pl, .lp	475$\times$1795	N	-	1443.33	-	?	-	-	-	Y	3.402	0.32	-
2-Insertions_5 .pl, .lp	597$\times$3936	N	45.08	0.50	6.97	?	-	-	-	?	-	-	-
DSJR500.1 .pl, .lp	500$\times$3555	N	0.53	0.18	0.18	N	2.78	0.21	0.18	N	-	0.26	0.19
DSJC500.1 .pl, .lp	500$\times$12458	N	2.19	0.45	0.64	N	12.30	0.57	0.76	N	6328.45	6.21	46.55
DSJR500.5 .pl, .lp	500$\times$58862	N	25.76	1.81	2.97	N	175.63	2.26	2.98	N	971.46	2.71	3.09
DSJC500.5 .pl, .lp	500$\times$62624	N	28.29	1.92	3.15	N	376.35	2.36	3.19	N	2707.64	2.84	3.47
DSJR500.1c .pl, .lp	500$\times$121275	N	84.19	3.66	6.07	N	1083.17	4.54	6.18	N	9881.35	5.50	6.19
DSJC500.9 .pl, .lp	500$\times$224874	N	74.44	3.39	5.67	N	543.02	4.29	5.67	N	3146.96	5.09	5.77
DSJC1000.1 .pl, .lp	1000$\times$49629	N	12.99	1.61	5.01	N	241.43	2.02	5.06	N	-	3.61	-
flat300_20_0 .pl, .lp	300$\times$21375	N	6.39	0.68	0.63	N	86.91	0.84	0.64	N	1555.37	1.08	0.69
flat300_26_0 .pl, .lp	300$\times$21633	N	6.45	0.70	0.65	N	131.91	0.87	0.67	N	3711.80	1.13	0.69
flat300_28_0 .pl, .lp	300$\times$21695	N	6.51	0.70	0.65	N	34.76	0.86	0.69	N	322.99	1.02	0.67
fpsol2.i.1 .pl, .lp	496$\times$11654	N	2.75	0.41	0.77	N	24.98	0.52	0.77	N	205.12	0.61	0.84
fpsol2.i.2 .pl, .lp	451$\times$8691	N	1.92	0.33	0.53	N	16.66	0.40	0.54	N	279.96	0.52	0.55
fpsol2.i.3 .pl, .lp	425$\times$8688	N	1.91	0.32	0.5	N	16.63	0.40	0.51	N	277.91	0.49	0.51
gen200_p0.9_44 .pl, .lp	200$\times$17910	N	5.53	0.57	0.36	N	30.87	0.70	0.36	N	306.81	0.84	0.38
gen200_p0.9_55 .pl, .lp	200$\times$17910	N	5.54	0.57	0.36	N	39.56	0.71	0.36	N	287.14	0.85	0.38
gen400_p0.9_55 .pl, .lp	400$\times$71820	N	38.91	2.19	2.88	N	656.07	2.68	2.89	N	4892.74	3.24	2.93
gen400_p0.9_65 .pl, .lp	400$\times$71820	N	39.02	2.16	2.88	N	275.33	2.67	2.87	N	1563.52	3.22	2.92
gen400_p0.9_75 .pl, .lp	400$\times$71820	N	38.87	2.17	2.88	N	270.12	2.70	2.89	N	1608.19	3.22	2.94
inithx.i.1 .pl, .lp	864$\times$18707	N	4.92	0.65	2.28	N	57.15	0.81	2.29	N	415.41	1.00	2.32
inithx.i.2 .pl, .lp	645$\times$13979	N	3.50	0.50	1.28	N	34.19	0.63	1.28	N	268.87	0.83	1.31
inithx.i.3 .pl, .lp	621$\times$13969	N	3.50	0.50	1.22	N	34.14	0.64	1.24	N	268.36	0.80	1.26
le450_5a .pl, .lp	450$\times$5714	N	0.85	0.24	0.26	N	9.06	0.29	0.28	Y	190.38	12.30	5.29
le450_5b .pl, .lp	450$\times$5734	N	0.85	0.24	0.29	N	7.77	0.29	0.3	Y	5146.86	0.98	0.48
le450_5c .pl, .lp	450$\times$9803	N	1.64	0.37	0.44	N	9.98	0.46	0.44	Y	217.77	0.70	0.03
le450_5d .pl, .lp	450$\times$9757	N	1.64	0.36	0.44	N	10.29	0.44	0.47	Y	530.63	0.60	0.08
mulsol.i.1 .pl, .lp	197$\times$3925	N	0.58	0.17	0.1	N	2.80	0.20	0.1	N	19.07	0.24	0.11
mulsol.i.2 .pl, .lp	188$\times$3885	N	0.57	0.17	0.1	N	2.83	0.20	0.09	N	31.25	0.24	0.11
mulsol.i.3 .pl, .lp	184$\times$3916	N	0.58	0.16	0.09	N	2.86	0.20	0.1	N	31.93	0.25	0.1
mulsol.i.4 .pl, .lp	185$\times$3946	N	0.58	0.17	0.1	N	2.92	0.20	0.1	N	32.83	0.25	0.11
mulsol.i.5 .pl, .lp	186$\times$3973	N	0.59	0.17	0.1	N	2.93	0.20	0.09	N	33.02	0.26	0.11
wap05a .pl, .lp	905$\times$43081	N	11.39	1.38	2.96	N	62.81	1.73	2.96	N	949.66	2.07	2.96
wap06a .pl, .lp	947$\times$43571	N	11.63	1.42	3.25	N	62.70	1.75	3.24	N	1326.84	2.13	3.26
wap07a .pl, .lp	1809$\times$103368	N	31.98	3.28	15.14	N	191.06	4.12	15.14	N	2861.64	4.99	15.19
wap08a .pl, .lp	1870$\times$104176	N	32.07	3.31	16.17	N	192.54	4.15	16.22	N	3604.96	5.08	16.18

Source of instances:COLOR02/03/04: Graph Coloring and its Applications

The $M$-$N$-Queens problem (`-' denotes no answer in 10 min. of CPU-time).

Instance		Solvability for $M=N-1$					Solvability for $M=N$					Solvability for $M=N+1$
$N$$V\times E$			SModels	CModels	CLP(FD)	ugraph		SModels	CModels	CLP(FD)	ugraph		SModels	CModels	CLP(FD)	ugraph
5 .pl, .lp	25$\times$320	N	0.06	0.07	0.01	0	Y	0.06	0.07	0.0	0	Y	0.07	0.08	0.0	0
6 .pl, .lp	36$\times$580	N	1.00	0.11	0.01	0	N	63.80	198.65	1.33	0.02	Y	0.66	0.19	0.0	0.16
7 .pl, .lp	49$\times$952	N	341.17	0.20	0.02	0.03	Y	1.95	0.18	0.0	0.29	Y	0.54	14.08	0.02	0.35
8 .pl, .lp	64$\times$1456	N	-	0.42	0.16	0.89	N	-	-	-	224.11	Y	116.50	1.28	1.04	807.22
9 .pl, .lp	81$\times$2112	N	-	0.85	1.37	106.64	?	-	-	-	-	Y	-	-	138.85	131.27
10 .pl, .lp	100$\times$2940	N	-	3.63	14.53	-	?	-	-	-	-	?	-	-	-	-
11 .pl, .lp	121$\times$3960	N	-	10.62	148.74	-	?	-	-	-	-	?	-	-	-	-

Source of instances:COLOR02/03/04: Graph Coloring and its Applications