Refined memorization for vertex cover

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.


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)

Actions (login required)

View Item View Item