Constructing an arborescence intuitively entails "e;folding"e; (i.e., overlapping) paths in a shortest-paths tree to yield the greatest possible wirelength savings while maintaining the shortest-paths property. For pointsets in the Manhattan plane, an effective arborescence heuristic is the construction of Rao et al. [14], which has a performance ratio of twice optimal, as well as good empirical performance (a variation of the method of [14] was given in [5]. However, these methods rely on the underlying geometry of the Manhattan metric. In order to handle FPGA routing graphs, we first define the notion of dominance in arbitrary weighted graphs as follows:

**Definition 3.1**
* Given a weighted graph G=(V,E), and nodes {n_0, p, s} in V,
we say that p* dominates *s if
minpath_G(n_0,p) = minpath_G(n_0,s) + minpath_G(s,p).*

Thus, `p` dominates `s` if a shortest path from the
source `n_0` to `p` can pass through `s`.
Note that the shortest path between a pair of nodes in an FPGA graph is
generally not unique. We define
`MaxDom(p,q)` as a node `m` in `V` dominated
by both `p` and `q` which maximizes
`minpath_G(n_0,m)`. Selecting a `MaxDom` as far away from
the origin as possible maximizes the overlap (i.e., the wirelength
savings) between the two paths.

These definitions enable our *Path-Folding Arborescence* (PFA)
heuristic which generalizes the method of
[14]
to arbitrary weighted graphs.
Starting with the set of nodes containing the source
and all sinks, find a pair of nodes `p` and `q` such that
`m=MaxDom(p,q)` is farthest away from the source among all such pairs;
then replace `p` and `q` by `m` and iterate
until only the source remains.
The graph Steiner arborescence solution is formed by using shortest paths in
`G` to connect each `MaxDom(p,q)` to both `p` and
`q` (Figure 5).

Path-Folding Arborescence (PFA) Algorithm

Input:Weighted graphG=(V,E)and netNsubset ofVOutput:A low-cost shortest-paths tree spanningN

M = NWhileN != {n_0}DoFinda pair{p,q}subset ofNsuch thatm = MaxDom(p,q)has maximumminpath_G(n_0,m)over all{p,q}inNN = {N - {p,q}}U{m}M = MU{m}Outputthe tree formed by connecting each nodepinM(using a shortest path inG) to the nearest node inMthatpdominates

Figure 5: Path-Folding Arborescence (PFA) heuristic.

Since there are at most `O(`|`N`|`)` elements in
set `N`, the time to compute all shortest-paths trees is bounded by
`O(`|`N`|`*`|`E`|`)`,
and the total number of `MaxDom` computations performed is at most
`O(`|`V`|`*`|`N`|`^2)`.
Storing the results of the `MaxDom` computations
in a heap allows the next `MaxDom` to be determined efficiently, and
results in an overall time complexity for PFA of
`O(`|`N`|`*`|`E`|` +`
|`V`|`*`|`N`|`^2 *
log`|`V`|`)`.

Our empirical results indicate that the PFA method is effective in
producing shortest-paths trees at a relatively modest wirelength
penalty. However, in considering the worst-case behavior of PFA, we
found examples of graphs where PFA can perform as badly as `O( N )`
times optimal. Thus, the next section presents another heuristic for
the graph arborescence problem which escapes such worst-case examples.