@inproceedings{591f6b1701994554ae21977149eee047,

title = "On the complexity of deadlock recovery",

abstract = "We consider the computational complexity of finding an optimal deadlock recovery. It is known that for an arbitrary number of resource types the problem is NP-hard even when the total cost of deadlocked jobs and the total number of resource units are “small” relative to the number of deadlocked jobs. It is also known that for one resource type the problem is NP-hard when the total cost of deadlocked jobs and the total number of resource units are “large” relative to the number of deadlocked jobs. In this paper we show that for one resource type the problem is solvable in polynomial time when the total cost of deadlocked jobs or the total number of resource units is “small” relative to the number of deadlocked jobs. For fixed m ≥ 2 resource types, we show that the problem is solvable in polynomial time when the total number of resource units is “small” relative to the number of deadlocked jobs. On the other hand, when the total number of resource units is “large”, the problem becomes NP-hard even when the total cost of deadlocked jobs is “small” relative to the number of deadlocked jobs. The results in this paper, together with previous known ones, give a complete delineation of the complexity of this problem under various assumptions of the input parameters.",

author = "Joseph Leung and Burkhard Monien",

year = "1985",

month = jan,

day = "1",

doi = "10.1007/BFb0024010",

language = "English (US)",

isbn = "9783540139126",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "208--218",

editor = "K. Mehlhorn",

booktitle = "STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science",

address = "Germany",

note = "2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 ; Conference date: 03-01-1985 Through 05-01-1985",

}