Can I read Alignment and Distribution Is Not (Always) NP-Hard on EtoBox?

Alignment and Distribution Is Not (Always) NP-Hard by Vincent Boudet; Fabrice Rastello; Yves Robert is a Computer Science article available to read on EtoBox.

What is Alignment and Distribution Is Not (Always) NP-Hard about?

In this paper, an efficient algorithm to simultaneously implement array alignment and dataÂcomputation distribution is introduced and evaluated. We revisit previous work of J. Li and M. Chen (in ``Frontiers 90: The Third Symposium on the Frontiers of Massively Parallel Computation, '' pp. 424 433, College Park MD, Oct. 1990; and J. Parallel Distrib. Comput. 13 (1991), 213 221), and we show that their alignment step should not be conducted without preserving the potential parallelism. In other words, the optimal alignment may well sequentialize computations, whatever the distribution afterward. We provide an efficient algorithm that handles alignment and dataÂcomputation distribution simultaneously. The good news is that several important instances of the whole alignment Âdistribution problem have polynomial complexity, while alignment itself is NP-complete (Li and Chen, 1990).

Who reads Alignment and Distribution Is Not (Always) NP-Hard?

Author

Vincent Boudet; Fabrice Rastello; Yves Robert

Publisher

Elsevier Science; Elsevier ; Elsevier Inc.; Elsevier BV (ISSN 0743-7315)

Published

2001

Language

EN

Field

Computer Science (Physical Sciences)