On the number of deadlock graphs

الملخص EN

The deadlock detection problem for serially-reusable, single-unit, single-request resources is equivalent to cycle detection in a bipartite graph.

A bipartite graph containing exactly one cycle represents a single deadlock.

There are many algorithms to detect a deadlock in this paper, we derive two formulas to determine the exact number of deadlock and non-deadlock graphs which are necessary to determine the complexity of a deadlock detection algorithm.