The searching over separators strategy to solve some NP-hard problems in subexponential time

In this paper we propose a new strategy for designing algorithms, called the searching over separators strategy. Suppose that we have a problem where the divide-and-conquer strategy can not be applied directly. Yet, also suppose that in an optimal solution to this problem, there exists a separator w...

Full description

Bibliographic Details
Published in:Algorithmica : an international journal in computer science, Vol. 9, No. 4 (1993), p. 398-423
Main Author: Hwang, Z.
Other Involved Persons: Chang, C. ; Lee, T.
Format: electronic Article
Language:English
ISSN:1432-0541
Item Description:This research work was partially supported by the National Science Council of the Republic of China under Grant NSC 79-0408-E007-04. Communicated by C. L. Liu.
Physical Description:Online-Ressource
DOI:10.1007/BF01228511
Subjects:
QR Code: Show QR Code