Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00134
A New Algorithm for Finding Minimal CycleBreaking Sets of Turns in a Graph
Vol. 10, no. 2, pp. 387420, 2006. Regular paper.
Abstract We consider the problem of constructing a minimal cyclebreaking set
of turns for a given undirected graph. This problem is important for
deadlockfree 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(N^{2}∆), 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 cyclebreaking sets
for connected graphs. Further, we construct minimal
cyclebreaking sets and establish
bounds on the minimum fraction of prohibited turns for two important
classes of graphs, namely, tpartite 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 wellknown and the widely used Up/Down
technique.
