Chandran, L. Sunil and Grandoni, Fabrizio (2005) Refined memorization for vertex cover. Information Processing Letters, 93 (3). pp. 123-131. ISSN 0020-0190
Full text not available from this repository.Abstract
Memorization is a technique which allows to speed up exponential recursive algorithms at the cost of an exponential space complexity. This technique already leads to the currently fastest algorithm for fixed-parameter vertex cover, whose time complexity is O(k1.2832k1.5+kn)O(1.2832kk1.5+kn), where n is the number of nodes and k is the size of the vertex cover. Via a refined use of memorization, we obtain an O(k1.2759k1.5+kn)O(1.2759kk1.5+kn) algorithm for the same problem. We moreover show how to further reduce the complexity to O(k1.2745k4+kn)
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Uncontrolled Keywords: | Memorization; Vertex cover; Computational complexity |
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 15:05 |
| Last Modified: | 24 May 2016 06:17 |
| URI: | http://repository.supsi.ch/id/eprint/4527 |
Actions (login required)
 |
View Item |