Solving large FPT problems on coarse-grained parallel machines
| Autor: | James J. Cheetham, Andrew Rau-Chaplin, Frank Dehne, Peter J. Taillon, Ulrike Stege |
|---|---|
| Rok vydání: | 2003 |
| Předmět: |
Sequence
Computer Networks and Communications Computer science Applied Mathematics 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Computational Theory and Mathematics Cover (topology) 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Parallelism (grammar) Code (cryptography) 020201 artificial intelligence & image processing Algorithm Computational biochemistry |
| Zdroj: | Journal of Computer and System Sciences. 67:691-706 |
| ISSN: | 0022-0000 |
| Popis: | Fixed-parameter tractability (FPT) techniques have recently been successful in solving NP-complete problem instances of practical importance which were too large to be solved with previous methods. In this paper, we show how to enhance this approach through the addition of parallelism, thereby allowing even larger problem instances to be solved in practice. More precisely, we demonstrate the potential of parallelism when applied to the bounded-tree search phase of FPT algorithms. We apply our methodology to the k-Vertex Cover problem which has important applications in, for example, the analysis of multiple sequence alignments for computational biochemistry. We have implemented our parallel FPT method for the k-Vertex Cover problem using C and the MPI communication library, and tested it on a 32-node Beowulf cluster. This is the first experimental examination of parallel FPT techniques. As part of our experiments, we solved larger instances of k-Vertex Cover than in any previously reported implementations. For example, our code can solve problem instances with k⩾400 in less than 1.5h. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect