Paper Info
Title
Solving large FPT problems on coarse-grained parallel machines
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 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.5 h.
Year
DOI
Venue
2003
10.1016/S0022-0000(03)00075-8
J. Comput. Syst. Sci.
Keywords
Field
DocType
larger instance,fpt algorithm,problem instance,coarse-grained parallel machine,parallel fpt technique,k-vertex cover problem,large fpt problem,parallel fpt method,k-vertex cover,32-node beowulf cluster,np-complete problem instance,larger problem instance,vertex cover,multiple sequence alignment,np complete problem
Combinatorics,Computer science,Theoretical computer science,Implementation
Journal
Volume
Issue
ISSN
67
4
Journal of Computer and System Sciences
Citations 
PageRank 
References 
43
2.66
16
Authors
5
Name
Order
Citations
PageRank
James Cheetham1553.84
Frank Dehne251843.70
Andrew Rau-chaplin363861.65
Ulrike Stege433434.26
Peter J. Taillon5564.87