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

Table 1: Impact of the main algorithmic components on N3A instance.

	Config (it)		Path built (%)	CPU time (s)	Feas. sol. (%)
Construction only	maxCount=1	without Dijkstra procedure	54	0.001	0
	maxCount=1	with Dijkstra procedure	81	0.001	0
	maxCount=1000	without Dijkstra procedure	79	0.06	0
	maxCount=1000	with Dijkstra procedure	96	0.03	9
	maxCount=100000	without Dijkstra procedure	86	6	0
	maxCount=100000	with Dijkstra procedure	100	6	100
Construction and improvement	maxCount=50 maxConstruct=1000 maxImprove=1000	without Dijkstra procedure	95	9.5	4
Construction and improvement	maxCount=50 maxConstruct=1000 maxImprove=1000	with Dijkstra procedure	100	0.7	100