Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00134
A New Algorithm for Finding Minimal Cycle-Breaking Sets of Turns in a Graph
Vol. 10, no. 2, pp. 387-420, 2006. Regular paper.
Abstract We consider the problem of constructing a minimal cycle-breaking set
of turns for a given undirected graph. This problem is important for
deadlock-free wormhole routing in computer and communication
networks, such as Networks of Workstations. The proposed Cycle
Breaking algorithm, or CB algorithm, guarantees that the constructed
set of prohibited turns is minimal and that the fraction of the
prohibited turns does not exceed 1/3 for any graph. The
computational complexity of the proposed algorithm is
O(N2∆), where N is the number of vertices, and ∆ is
the maximum node degree. The memory complexity of the algorithm is
O(N∆).
We provide lower bounds on the minimum size of cycle-breaking sets
for connected graphs. Further, we construct minimal
cycle-breaking sets and establish
bounds on the minimum fraction of prohibited turns for two important
classes of graphs, namely, t-partite graphs and graphs with small
degrees. The upper bounds are tight and demonstrate the optimality
of the CB algorithm for certain classes of graphs. Results of
computer simulations illustrate the superiority of the proposed CB
algorithm as compared to the well-known and the widely used Up/Down
technique.
|
Journal Supporters
|