An Efficient Parallel Algorithm for Solving the 3-Partition Problem Based on ADI
Tahere Panahi1, Tahere Heidari2, Vahid Sattari Naeini3
1Tahere Panahi, Department of Computer Engineering, Kerman Branch, Islamic Azad University, Kerman, Iran.
2Tahere Heidari, Department of Computer Engineering, Kerman Branch, Islamic Azad University, Kerman, Iran.
3Vahid Sattari Naeini, Department of Computer Engineering, University of Kerman, A failproof Square, Kerman, Iran.
Manuscript received on 21 March 2013 | Revised Manuscript received on 28 March 2013 | Manuscript published on 30 March 2013 | PP: 94-98 | Volume-2 Issue-1, March 2013 | Retrieval Number: B0619052213/2013©BEIESP
Open Access | Ethics and Policies | Cite | Mendeley | Indexing and Abstracting
© The Authors. Blue Eyes Intelligence Engineering and Sciences Publication (BEIESP). This is an open access article under the CC-BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/)
Abstract: The three-partition problem is one of the most famous strongly NP-complete combinatorial problems. Most of the recently proposed computational methods for solving partial differential equations on multiprocessor architectures stem from the ‘divide and conquer’ paradigm and involve some form of domain decomposition. For those methods which also require grids of points or patches of elements, it is often necessary to explicitly partition the underlying mesh, especially when working with local memory parallel processors. In this paper, a family of cost-effective algorithms for the automatic partitioning of arbitrary two- and three-dimensional finite element and finite difference meshes is presented and discussed in view of a domain decomposed solution procedure and parallel processing. We introduce properties which, in many cases, can allow either a quick solution of an instance or a reduction of its size. The average effectiveness of the properties proposed is tested through computational experiments. In this paper we propose a new approach to organize a parallel computing for finding all solutions of a problem, whose sequential algorithm takes too long finding all solutions. The parallel computing organization above presented is an combination of the bottom-up design and the divide and conquer design. We also propose a new efficient and simple algorithm for the 3-partition problem and paralellize the algorithm.
Keywords: Three Partition Problem, Dynamic Programming, NP Complete, Divide.
Scope of the Article: Foundations Dynamics