5. Iterated Dominance Heuristic

Our second heuristic for the GSA problem greedily iterates over a given spanning arborescence construction: we repeatedly find Steiner candidates that reduce the overall spanning arborescence cost, and include them into the growing set of Steiner nodes. The heuristic which we use for producing spanning arborescences is the Dominating (DOM) heuristic, described as follows:

• DOM -- connect each sink to the closest sink or source that it dominates, and compute the shortest-paths tree over the union of these paths.

Definition 5.1 Given a set of Steiner candidate node S subset of V - N, we define the cost savings of S with respect to DOM as Delta DOM( G, N, S ) = cost(DOM( G, N)) - cost(DOM(G, N U S )).

Starting with an initially empty set of Steiner candidates S = Ø, our heuristic finds a node t in V - N which maximizes Delta DOM( G, N, S U { t } ) > 0 and repeats this procedure with S = S U { t }. The cost for DOM to span N U S will decrease with each added node t, and the construction terminates when there is no t in (V - N) - S such that Delta DOM( G, N, S U { t } ) > 0, with the final solution being DOM( G, N U S ). This Iterated Dominance (IDOM) approach is formally described in Figure 6. The IDOM heuristic can be implemented within time O(|N|*|E| + |V|*|N|^3 ).

Iterated Dominance (IDOM) Algorithm 

Input: A weighted graph G=(V,E) and a net N subset of V
Output: Low-cost arborescence T'=(V',E') spanning N, where
        N subset of V' subset of V and E' subset of E

S = Ø
Do Forever
    T = { t in V - N | Delta DOM( G, N, S U {t}) > 0 }
    If T = Ø Then Return DOM(G, N U S)
    Find t in T with maximum Delta DOM( G, N, S U {t})
    S = S U {t}

        Figure 6: The Iterated Dominance algorithm.