Name
Abstract | ||
|---|---|---|
Fixed-parameter tractability (FPT techniqueshave recently been successful in solving NP-completeproblem instances of practical importance which weretoo large to be solved with previous methods. Inthis paper we show how to enhance this approachthrough the addition of parallelism, thereby allowingeven larger problem instances to be solved in practice. More precisely, we demonstrate the potential ofparallelism when applied to the bounded-tree searchphase of FPT algorithms. We apply our methodology to the k-VERTEX COVER problem which has important applications, e.g., in multiple sequence alignments for computational biochemistry. We have implemented our parallel FPT method for the k-VERTEXCOVER problem using C and the MPI communicationlibrary, and tested it on a PC cluster. This is the firstexperimental examination of parallel FPT techniques.We have tested our parallel k-VERTEX COVER methodon protein sequences obtained from the National Center for Biotechnology Information. As part of our experiments, we solved larger instances of k-VERTEXCOVER than in any previously reported implementations. For example, our code can solve problem instances with k \ge 400 in less than 1.5 hours. Since ourparallel FPT algorithm requires only very little communication between processors, we expect our methodto also perform well on Grids. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/CCGRID.2003.1199354 | CCGrid |
Keywords | Field | DocType |
grid computing,optimisation,parallel algorithms,workstation clusters,MPI communication library,NP-complete problem,PC cluster,computational biochemistry,fixed-parameter tractability technique,grid computing,k- VERTEX COVER method,parallel FPT method | Cluster (physics),NP-complete,Grid computing,Parallel algorithm,Computer science,Parallel processing,Algorithm,Concurrent computing,Workstation clusters,Cluster analysis,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-7695-1919-9 | 1 | 0.36 |
References | Authors | |
12 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| James Cheetham | 1 | 55 | 3.84 |
| Frank Dehne | 2 | 518 | 43.70 |
| Andrew Rau-chaplin | 3 | 638 | 61.65 |
| Ulrike Stege | 4 | 334 | 34.26 |
| Peter J. Taillon | 5 | 56 | 4.87 |