Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 671-677 |
Number of pages | 7 |
Journal | IEEE Transactions on Computers |
Volume | C-28 |
Issue number | 9 |
DOIs | |
State | Published - Sep 1979 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computational Theory and Mathematics