Optimizing the Cyclic K-conflict-free Shortest Path Problem in a Network-on-chip : Table 2

Table 2: Comparative results on the whole benchmark set.
^a Time per run in Intel Core Duo (3.0 GHz) seconds (1 core used), C++ program. ^b Time per run in Intel core i3-2350M (2.30 GHzx4) seconds, GLPK program.

			N1(6-7-4-12)	N2(8-9-7-28)	N3A(9-15-10-27)	N3B(9-15-10-24)	N4(47-36-35-209)	average	deviation
neighborhood large	IRS	time^a length	0.002 53.3	0.11 119.5	0.70 131.7	0.82 119.6	8.89 1565	2.1 398	(±0.14) (±3.5)
	ILS-FI	time^a length	0.001 53.5	0.15 117.8	0.69 129.8	0.84 118.6	7.25 1570	1.79 398	(±0.1) (±3.5)
	ILS-BI	time^a length	0.001 53.7	0.17 119.0	0.66 127.1	0.85 118.0	7.57 1568	1.85 397	(±0.13) (±3)
neighborhood medium	IRS	time^a length	0.003 52.92	0.11 121.12	0.58 132.05	0.68 120.87	8.71 1572.80	2.01 400	(±0.16) (±3.48)
	ILS-FI	time^a length	0.001 52.86	0.18 118.24	0.74 128.70	0.81 117.37	6.97 1568.66	1.74 397	(±0.11) (±2.74)
	ILS-BI	time^a length	0.00 54.66	0.18 118.48	0.74 127.72	0.87 117.88	7.06 1574.62	1.77 399	(±0.10) (±2.91)
neighborhood small	IRS	time^a length	0.002 52.8	0.17 118.9	0.61 132.9	0.61 120.3	6.50 1577	1.58 400	(±0.08) (±3.89)
	ILS-FI	time^a length	0.001 53.73	0.22 119.88	1.44 130.85	1.81 118.84	7.35 1566.04	2.16 398	(±0.12) (±3.25)
	ILS-BI	time^a length	0.001 54.57	0.20 119.24	1.37 129.15	1.44 118.80	7.45 1567.36	2.09 398	(±0.13) (±3.19)
ILP	first-sol	time^b length	5 57	428 133	- -	- -	- -	- -	- -
ILP	opt-sol	time^b length	111 42	1464 76	- -	- -	- -	- -	- -