An Efficient Parallel Algorithm for Solving the 3-Partition Problem Based On ADI

The three-partition problem is one of the mostfamous strongly NP-complete combinatorial problems. Most ofthe recently proposed computational methods for solving partialdifferential equations on multiprocessor architectures stem fromthe 'divide and conquer' paradigm and involve some form ofdomain decomposition. For those methods which also requiregrids of points or patches of elements, it is often necessary toexplicitly partition the underlying mesh, especially when workingwith local memory parallel processors. In this paper, a family ofcost-effective algorithms for the automatic partitioning ofarbitrary two- and three-dimensional finite element and finitedifference meshes is presented and discussed in view of a domaindecomposed solution procedure and parallel processing. Weintroduce properties which, in many cases, can allow either aquick solution of an instance or a reduction of its size. Theaverage effectiveness of the properties proposed is tested throughcomputational experiments. In this paper we propose a newapproach to organize a parallel computing for finding allsolutions of a problem, whose sequential algorithm takes too longfinding all solutions. The parallel computing organization abovepresented is an combination of the bottom-up design and thedivide and conquer design. We also propose a new efficient andsimple algorithm for the 3-partition problem and paralellize thealgorithm.