A New Algorithm for Finding Minimal Cycle-Breaking Sets of Turns in a Graph - Levitin, Lev; Karpovsky, Mark; Mustafa, Mehmet; Zakrevski, Lev (Journal of Graph Algorithms and Applications, 2006)
We consider the problem of constructing a minimal cycle-breaking setof turns for a given undirected graph. This problem is important fordeadlock-free wormhole routing in computer and communicationnetworks, such as Networks of Workstations. The proposed CycleBreaking algorithm, or CB algorithm, guarantees that the constructedset of prohibited turns is minimal and that the fraction of theprohibited turns does not exceed 1/3 for any graph. Thecomputational complexity of the proposed algorithm isO(N2∆), where N is the number of vertices, and ∆ isthe maximum node degree. The memory complexity of the algorithm isO(N∆).We provide lower bounds on the minimum size of cycle-breaking setsfor connected graphs. Further, we construct minimalcycle-breaking sets and establishbounds on the minimum fraction of prohibited turns for two importantclasses of graphs, namely, t-partite graphs and graphs with smalldegrees. The upper bounds are tight and demonstrate the optimalityof the CB algorithm for certain classes of graphs. Results ofcomputer simulations illustrate the superiority of the proposed CBalgorithm as compared to the well-known and the widely used Up/Downtechnique. <!---->