Abstract
We present the first investigation of the well-known memorization technique for solving the k -Vertex Cover problem in a distributed setting. Memorization was introduced by Robson [15] in his paper on solving the Maximum Independent Set problem. The idea is to augment a recursive algorithm with the capability to store subproblem instances and solutions of bounded size in a table that can be quickly referenced, so that subproblems are guaranteed to be solved exactly once. This approach has recently been applied with success to improve the complexity of the fixed-parameter tractable algorithms for solving the k -Vertex Cover problem [12,5]. We present a general parallel approach for using memorization to solve the k -Vertex Cover problem where the subgraphs are precomputed [12]. In this case, the subgraphs and corresponding solutions are generated in a preprocessing step, rather than during the recursion. Our technique makes efficient use of the processors generating the lookup table, while at the same time requiring less space. We describe a distributed algorithm using this technique, well-suited to cluster or grid computing platforms.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abu-Khzam, F.N., Langston, M.A., Shanbhag, P., Symons, C.T.: Scalable parallel algorithms for FPT problems. Algorithmica 45, 269–284 (2006)
Abu-Khzam, F.N., Collins, R.L., Fellows, M.R., Langston, M.A., Suters, W.H., Symons, C.T.: Kernelization algorithms for the vertex cover problem: Theory and experiments. In: ALENEX. Proceedings of the ACM-SIAM Workshop on Algorithm Engineering and Experiments, pp. 62–69. ACM Press, New York (2004)
Akl, S.G., Gries, D.R., Stojmenović, I.: An optimal parallel algorithm for generating combinations. Information Processing Letters 33, 135–139 (1990)
Baldwin, N.E., Collins, R.L., Leuze, M.R., Langston, M.A., Symons, C.T., Voy, B.H.: High-performance computational tools for motif discovery. In: Proceedings of the IEEE International Workshop on High Performance Computational Biology, pp. 192–199. IEEE Computer Society Press, Los Alamitos (2004)
Chandran, L.S., Grandoni, F.F.: Refined memorization for vertex cover. Information Processing Letters 93, 125–131 (2005)
Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.J.: Solving large FPT problems on coarse grained parallel machines. Journal of Computer and System Sciences 67, 691–706 (2003)
Cheetham, J., Dehne, F., Rau-Chaplin, A., Stege, U., Taillon, P.J.: A parallel FPT application for clusters. In: CCGrid. Proceedings of the IEEE-ACM International Symposium on Cluster Computing and the Grid, pp. 70–77. IEEE Computer Society Press, Los Alamitos (2003)
Chen, J., Kanj, I.A., Xia, G.: Improved parameterized upper bounds for VERTEX COVER. In: The 31st International Symposium on Mathematical Foundations of Computer Science (MFC), pp. 238–249 (2006)
Dehne, F.: Guest editor’s introduction. Algorithmica Special Issue on Coarse Grained Parallel Algorithms 24, 173–176 (1999)
Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1998)
Karp, R.: Reducibility among combinatorial problems. Complexity of Computer Computations, pp. 85–104. Plenum Press, New York (1972)
Niedermeier, R., Rossmanith, P.: On efficient fixed-parameter algorithms for weighted vertex cover. Journal of Algorithms 47, 63–77 (2003)
Pinchak, C., Lu, P., Schaeffer, J., Goldenberg, M.: Practical heterogeneous placeholder scheduling in overlay metacomputers: Early experiences. In: Feitelson, D.G., Rudolph, L., Schwiegelshohn, U. (eds.) JSSPP 2002. LNCS, vol. 2537, pp. 85–105. Springer, Heidelberg (2002)
Pinchak, C., Lu, P., Schaeffer, J., Goldenberg, M.: The Canadian Internetworked Scientific Supercomputer. In: Proceedings of the 17th Annual International Symposium on High Performance Computing Systems and Applications (HPCS), pp. 193–199 (2003)
Robson, J.M.: Algorithms for maximum independent sets. Journal of Algorithms 7, 425–440 (1986)
Robson, J.M.: Finding a maximum independent set in time O(2n/4). Technical Report LaBRI Université Bordeaux I 1251-01 (2001)
Stojmenović, I.I.: Listing combinatorial objects in parallel. International Journal of Parallel, Emergent and Distributed Systems 21, 127–146 (2006)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2007 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Taillon, P.J. (2007). Distributed Memorization for the k -Vertex Cover Problem. In: Stojmenovic, I., Thulasiram, R.K., Yang, L.T., Jia, W., Guo, M., de Mello, R.F. (eds) Parallel and Distributed Processing and Applications. ISPA 2007. Lecture Notes in Computer Science, vol 4742. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-74742-0_16
Download citation
DOI: https://doi.org/10.1007/978-3-540-74742-0_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-74741-3
Online ISBN: 978-3-540-74742-0
eBook Packages: Computer ScienceComputer Science (R0)