Networks of Workstations (NOWs) are usually arranged as a set of interconnected switches with hosts connected to switch ports through interface cards. Several commercial interconnects for high-speed NOWs use up*/down* routing. Every time the network is powered on or the topology is changed, a configuration algorithm is executed, which provides information about the topology and generates a directed graph. Routing tables are computed from this directed graph. There are several ways to obtain the directed graph. The most frequent way is by means of algorithms based on minimum-depth spanning-trees (MDST) or propagation-order spanning-trees (POST). This paper shows that, for most networks, graphs obtained by means of these methods can be improved in order to achieve higher network performance.