TWO-PHASE HEURISTIC FOR CAPACITATED DEGREE CONSTRAINED MIN-SUM ARBORESCENCE

We present a two-phase heuristic for designing a capacitated degree constrained min sum arborescence. For a given directed graph G(V,E) where V={0, 1,…,n} with nonnegative costs Cij for each (i,j) ? E, our heuristic finds a minimum cost arborescence rooted at node 1 that spans the set {0, 1,…,n} with a constraint that the number of edges incident on each node i ? {1,2,…,n} is limited to a predetermined number constrained by the number of ports available on them (degree constraint). Additionally, the polling and response time constraints limit the number of nodes in the sub-trees rooted at node 1 (capacity constraint) predefined number. Lower bounds given for the integer programming formulation of the problem by our heuristic is used to estimate the quality of the solutions. Experimental results over a wide range of problem structures show that the two-phase heuristic gives verifiably good solutions to this problem.