On Minimum Cost Recovery from System Deadlock

Joseph Y.T. Leung, Edmund K. Lai

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


In this paper we consider the problem of finding a minimum cost deadlock recovery. We show that the problem is NP-complete and hence an efficient algorithm is unlikely to exist for this problem. We propose three fast heuristics and analyze their worst case performance relative to optimal solutions. Finally, we perform some simulation tests to get a feel for the average performance of these heuristics.

Original languageEnglish (US)
Pages (from-to)671-677
Number of pages7
JournalIEEE Transactions on Computers
Issue number9
StatePublished - Sep 1979
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'On Minimum Cost Recovery from System Deadlock'. Together they form a unique fingerprint.

Cite this