𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Solving large FPT problems on coarse-grained parallel machines

✍ Scribed by James Cheetham; Frank Dehne; Andrew Rau-Chaplin; Ulrike Stege; Peter J. Taillon

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
208 KB
Volume
67
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

✦ Synopsis

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 kX400 in less than 1:5 h:

πŸ“œ SIMILAR VOLUMES

Random Data Accesses on a Coarse-Grained
Random Data Accesses on a Coarse-Grained Parallel Machine I. One-to-One Mappings
✍ Ravi V. Shankar; Sanjay Ranka πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 271 KB

This paper describes deterministic communication-efficient algorithms for performing dynamic permutations on a coarsegrained parallel machine. Our analysis shows that the general permutation operation can be completed in CΒ΅n/p (+ lower order terms) time and is optimal and scalable provided n >> p 3

Random Data Accesses on a Coarse-Grained
Random Data Accesses on a Coarse-Grained Parallel Machine II. One-to-Many and Many-to-One Mappings
✍ Ravi V. Shankar; Sanjay Ranka πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 290 KB

This paper describes deterministic communication-efficient algorithms for performing random data accesses with hot spots on a coarse-grained parallel machine. The general random access read-write operations with hot spots can be completed in CΒ΅n/p (+ lower order terms) time and is optimal and scalab

FINITE ELEMENT ALGORITHMS FOR DYNAMIC SI
FINITE ELEMENT ALGORITHMS FOR DYNAMIC SIMULATIONS OF VISCOELASTIC COMPOSITE SHELL STRUCTURES USING CONJUGATED GRADIENT METHOD ON COARSE GRAINED AND MASSIVELY PARALLEL MACHINES
✍ SUNG YI; M. FOUAD AHMAD; HARRY H. HILTON πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 237 KB πŸ‘ 2 views

Recently much attention has been paid to high-performance computing and the development of parallel computational strategies and numerical algorithms for large-scale problems. In this present study, a ΓΏnite element procedure for the dynamic analyses of anisotropic viscoelastic composite shell struct

A Data Parallel Algorithm for Solving th
A Data Parallel Algorithm for Solving the Region Growing Problem on the Connection Machine
✍ N. Copty; S. Ranka; G. Fox; R.V. Shankar πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 696 KB

Region growing is a general technique for image segmentation, where image characteristics are used to group adjacent pixels together to form regions. This paper presents a parallel algorithm for solving the region growing problem based on the split-andmerge approach, and uses it to test and compare