Refined memorization for vertex cover |
| |
Authors: | L Sunil Chandran |
| |
Affiliation: | Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany |
| |
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), 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) algorithm for the same problem. We moreover show how to further reduce the complexity to O(k1.2745k4+kn). |
| |
Keywords: | Memorization Vertex cover Computational complexity |
本文献已被 ScienceDirect 等数据库收录! |
|