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 graphG=(V,E)and a netNsubset ofVOutput:Low-cost arborescenceT'=(V',E')spanningN, whereNsubset ofV'subset ofVandE'subset ofE

S =ØDo ForeverT = { tinV - N|DeltaDOM( G, N, SU{t}) > 0 }IfT =ØThen ReturnDOM(G, NUS)FindtinTwith maximumDeltaDOM( G, N, SU{t})S = SU{t}

Figure 6: The Iterated Dominance algorithm.