DIMACS TR: 99-18
On Lower Bound of the Number of Channels for Deadlock-Free
Authors: Li Sheng and Jie Wu
Libeskind-Hadas recently provided a tight lower bound on the number of
channels required by a broad class of deadlock-free wormhole routing
algorithm. Given an interconnection network represented by a digraph
$G=(N,C)$, where each vertex in $N$ represents a node and each
directed link in $C$ represents a unidirectional channel,
Libeskind-Hadas showed that $|C|\ge 2|N|-2$ is the tight lowered on
the number of Channels required for Deadlock-Free Whormhole Routing.
In this short note, we show a simpler proof of this tight lower bound.
Paper Available at:
DIMACS Home Page