|
Published Articles >> Table of Contents >> Abstract
Third IEEE International Symposium on Cluster Computing and the Grid (CCGrid'03)
p. 70
A Parallel FPT Application For Clusters
James Cheetham, Carleton University
Frank Dehne, Carleton University
Andrew Rau-Chaplin, Dalhousie University
Ulrike Stege, University of Victoria
Peter J. Taillon, Carleton University
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/CCGRID.2003.1199354
Send link to a friend
| Abstract |
|
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, e.g., in 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 PC cluster. This is the first
experimental examination of parallel FPT techniques.
We have tested our parallel k-VERTEX COVER method
on protein sequences obtained from the National Center for Biotechnology Information. 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 \ge 400 in less than 1.5 hours. Since our
parallel FPT algorithm requires only very little communication between processors, we expect our method
to also perform well on Grids.
|
 Additional Information
|
Index Terms- Fixed-Parameter Tractatbility, k-Vertex
Cover, Computational Biochemistry
Citation:
James Cheetham, Frank Dehne, Andrew Rau-Chaplin, Ulrike Stege, Peter J. Taillon,
"A Parallel FPT Application For Clusters,"
ccgrid,
p. 70,
Third IEEE International Symposium on Cluster Computing and the Grid (CCGrid'03),
2003
|
|
