Graph COloring

Benchmarks results

Instances	|v|	ρ	Backtrack (g.V)			Backtrack (k+1)			Branch and Bound				Heuristic		Sol
			Execution time	Explored solutions	K	Execution time	Explored solutions	K	Execution time	Explored solutions	Branched solution	K	Execution time	K
test1	3	33.333%	41.387µs	6	3	40.38µs	4	3	42.889µs	0	2	3	7.395µs	3	3
test2	4	31.250%	87.161µs	36	3	61.906µs	11	3	51.592µs	0	2	3	8.142µs	3	3
test3	5	28.000%	235.915µs	80	3	73.871µs	14	3	114.795µs	0	10	3	9.616µs	3	3
myciel3	11	16.529%	722.450ms	249,460	4	13.187ms	4,668	4	3.387ms	80	987	4	11.467µs	4	4
myciel4	23	13.422%	~72h	48,694,100,000	-	44m52.565s	787,863,524	5	15.257s	505,200	3,699,368	5	23.854µs	5	5
myciel5	47	10.684%	-	-	-	-	-	-	~7h	4,237,329,722	341,000,000	-	49.131µs	6	6
queen5_5	25	51.200%	9.355s	6,369	5	25.622ms	1,692	5	564.316µs	0	9	5	33.288µs	5	5
queen6_6	36	44.753%			-	3m42.257s	439,764	7	5.141s	3	202,762	7	54.639µs	9	7
queen7_7	49	39.650%			-	9m1.7289s	3,617,667	-	12.487s	59	371.844	7	95.529µs	12	7

Instances	|v|	ρ	Heuristic		Heuristic+		Pseudo Random Heuristic		Sol
			Execution time	K	Execution time	K	Execution time	K
test1	3	33.333%	7.395µs	3	9.952µs	3	2.374s	3	3
test2	4	31.250%	8.142µs	3	9.754µs	3	2.774s	3	3
test3	5	28.000%	9.616µs	3	10.100µs	3	3.525s	3	3
myciel3	11	16.529%	11.467µs	4	13.473µs	4	5.871s	4	4
myciel4	23	13.422%	23.854µs	5	27.353µs	5	11.803s	5	5
myciel5	47	10.684%	49.131µs	6	49.783µs	6	11.803s	6	6
queen5_5	25	51.200%	33.288µs	5	39.337µs	5	15.211s	5	5
queen6_6	36	44.753%	54.639µs	9	53.845µs	9	24.431s	7	7
queen7_7	49	39.650%	95.529µs	12	00.531µs	12	33.801s	9	7
2-Insertions_3	37	5.259%	31.871µs	4	30.060µs	4	17.489s	4	4
homer	561	1.035%	1.222ms	13	5m8.507s	13	5m8.507s	13	13
fpsol2.i.1	496	4.737%	13.319ms	65	10.380ms	65	47m19.180s	65	56
fpsol2.i.2	451	4.273%	4.721ms	30	3.698ms	30	-	(30)	30
fpsol2.i.3	425	4.810%	4.642ms	30	3.678ms	30	-	(30)	30
inithx.i.1	864	2.506%	19.821ms	54	11.161ms	54	-	(54)	54
qg.order30	900	3.222%	12.977ms	32	10.037ms	32	-	(32)	30
qg.order100	10000	0.990%	1.694s	128	1.239s	128	-	(128)	100

Results details

test1.col

g.v

sol=[3 2 1] min=3
exploredSolutions=6
2018/11/24 18:00:19 backtrack took 41.387µs

k+1

sol=[2 3 1] min=3
exploredSolutions=4
2018/11/24 18:04:22 backtrack took 40.38µs

bab

sol=[1 2 3] min=3
exploredSolutions=0
branchedSolutions=2
2018/11/27 01:01:49 branch and bound took 42.889µs

greedy

sol=[1 3 2] k=3
2018/11/24 18:06:16 greedy took 7.395µs

test2.col

g.v

sol=[4 3 4 1] min=3
exploredSolutions=36
2018/11/24 18:01:25 backtrack took 87.161µs

k+1

sol=[2 3 2 1] min=3
exploredSolutions=11
2018/11/24 18:03:23 backtrack took 61.906µs

bab

sol=[1 2 1 3] min=3
exploredSolutions=0
branchedSolutions=2
2018/11/27 01:01:32 branch and bound took 51.592µs

greedy

sol=[3 1 3 2] k=3
2018/11/24 18:06:46 greedy took 8.142µs

test3.col

g.v

sol=[5 5 4 3 1] min=3
exploredSolutions=80
2018/11/24 18:02:29 backtrack took 235.915µs

k+1

sol=[2 2 3 4 1] min=3
exploredSolutions=14
2018/11/24 18:02:57 backtrack took 73.871µs

bab

sol=[1 1 2 3 2] min=3
exploredSolutions=0
branchedSolutions=10
2018/11/27 01:00:00 branch and bound took 114.795µs

greedy

sol=[1 1 2 3 2] k=3
2018/11/24 18:07:36 greedy took 9.616µs

myciel3.col

g.V

sol=[11 10 11 10 9 11 10 11 10 9 1] min=4
exploredSolutions=249460
2018/11/27 01:13:08 backtrack took 722.450603ms

k+1

sol=[2 3 2 3 4 4 4 2 3 4 1] min=4
exploredSolutions=4668
2018/11/27 01:12:49 backtrack took 13.187563ms

bab

sol=[2 3 2 3 1 2 3 2 3 1 4] min=4
exploredSolutions=80
branchedSolutions=987
2018/11/27 00:59:34 branch and bound took 3.387112ms

greedy

sol=[1 2 3 2 1 3 2 3 2 4 1] k=4
2018/11/24 18:08:56 greedy took 11.467µs

myciel4.col

g.V

exploredSolutions=48694100000
~72h

k+1

sol=[2 3 2 3 4 4 4 2 3 4 5 5 5 5 5 5 4 4 2 3 4 5 1] min=5
exploredSolutions=787863524
2018/11/16 23:16:11 backtrack took 44m52.565025305s

bab

sol=[2 3 2 3 4 4 4 2 3 4 1 2 3 2 3 4 4 4 2 3 4 1 5] min=5
exploredSolutions=505200
branchedSolutions=3699368
2018/11/27 00:59:16 branch and bound took 15.257577355s

greedy

sol=[1 2 3 2 1 3 4 3 3 4 1 5 2 3 2 4 3 2 3 2 4 2 1] k=5
2018/11/24 18:08:22 greedy took 23.854µs

myciel5.col

g.V

-

k+1

exploredSolutions=534800000
~1h

bab

exploredSolutions=341000000
branchedSolutions=4237329722
~7h

greedy

sol=[2 1 3 1 2 2 5 3 3 2 1 4 4 3 3 4 6 5 3 3 5 4 1 2 5 3 3 2 2 5 3 3 2 4 2 4 3 3 2 2 4 3 3 2 4 2 1] k=6
2018/11/24 18:09:14 greedy took 49.131µs

queen5_5

g.V

sol=[5 4 3 2 1 3 2 1 5 4 1 5 4 3 2 4 3 2 1 5 2 1 5 4 3] min=5
exploredSolutions=6369
2018/11/19 22:01:24 backtrack took 9.354607749s

k+1

sol=[2 3 4 5 1 5 1 2 3 4 3 4 5 1 2 1 2 3 4 5 4 5 1 2 3] min=5
exploredSolutions=1692
2018/11/19 22:44:58 backtrack took 25.622095ms

bab

sol=[1 2 3 4 5 3 4 5 1 2 5 1 2 3 4 2 3 4 5 1 4 5 1 2 3] min=5
exploredSolutions=0
branchedSolutions=9
2018/11/27 01:02:07 branch and bound took 564.316µs

greedy

sol=[2 3 4 1 5 1 5 2 3 4 3 4 1 5 2 5 2 3 4 1 4 1 5 2 3] k=5
2018/11/24 18:10:45 greedy took 33.288µs

queen6_6

g.v

k+1

sol=[2 3 4 5 6 7 7 5 6 3 2 1 6 4 7 1 5 3 3 1 5 4 7 2 5 6 3 2 1 4 4 2 1 7 3 6] min=7
exploredSolutions=439764
2018/11/19 22:07:43 backtrack took 3m42.257375417s

bab

sol=[1 2 3 4 5 6 3 4 5 6 7 1 5 6 7 1 2 3 7 1 2 3 4 5 2 3 4 5 6 7 4 5 6 7 1 2] min=7
exploredSolutions=3
branchedSolutions=202762
2018/11/27 01:02:32 branch and bound took 5.1413681s

greedy

sol=[8 2 7 5 1 9 5 1 3 6 4 7 9 6 4 1 2 3 1 5 2 3 6 4 2 3 1 4 5 8 6 4 5 7 3 2] k=9
2018/11/24 18:11:25 greedy took 54.639µs

queen7_7

g.v

k+1

sol=[2 3 4 5 6 7 1 7 1 2 3 4 5 6 5 6 7 1 2 3 4 3 4 5 6 7 1 2 1 2 3 4 5 6 7 6 7 1 2 3 4 5 4 5 6 7 1 2 3] min=7
exploredSolutions=3617667
backtrack took 9m1.728700528s

bab

sol=[1 2 3 4 5 6 7 3 4 5 6 7 1 2 5 6 7 1 2 3 4 7 1 2 3 4 5 6 2 3 4 5 6 7 1 4 5 6 7 1 2 3 6 7 1 2 3 4 5] min=7
exploredSolutions=59
branchedSolutions=371844
2018/11/27 01:03:03 branch and bound took 12.487382662s

greedy

sol=[12 4 3 8 6 5 7 8 5 6 7 1 3 4 9 1 2 3 4 6 5 7 3 4 1 5 2 9 4 6 5 2 3 1 8 11 2 1 6 7 4 10 10 7 8 4 2 9 6] k=12
2018/11/24 18:11:42 greedy took 95.529µs