Paper Info
Title
Design and Use of the CPAN Branch & Bound for the Solution of the Travelling Salesman Problem (TSP)
Abstract
This article presents the design of a High Level Parallel Composition or CPAN (according to its Spanish acronym) that implements a parallelization of the algorithmic design technique named Branch & Bound and uses it to solve the Travelling Salesman Problem (TSP), within a methodological infrastructure made up of an environment of Parallel Objects, an approach to Structured Parallel Programming and the Object-Orientation paradigm. A CPAN is defined as the composition of a set of parallel objects of three types: one object manager, the stages and the Collector objects. By following this idea, the Branch & Bound design technique implemented as an algorithmic parallel pattern of communication among processes and based on the model of the CPAN is shown. Thus, in this work, the CPAN Branch & Bound is added as a new pattern to the library of classes already proposed in [9], which was initially constituted by the CPANs Farm, Pipe and TreeDV that represent, respectively, the patterns of communication Farm, Pipeline and Binary Tree, the latter one implementing the design technique known as Divide and Conquer. As the programming environment used to derive the proposed CPANs, we use C++ and the POSIX standard for thread programming.
Year
DOI
Venue
2005
10.1109/CONIEL.2005.33
international conference on electronics, communications, and computers
Keywords
Field
DocType
parallel objects,structured parallel programming,high performance computing,object oriented programming,concurrent programming.
Branch and bound,Algorithm design,Object-oriented programming,Computer science,Parallel algorithm,Tree (data structure),Binary tree,Theoretical computer science,Travelling salesman problem,Divide and conquer algorithms
Conference
ISSN
ISBN
Citations 
2474-9036
0-7695-2283-1
6
PageRank 
References 
Authors
0.55
0
2
Name
Order
Citations
PageRank
Manuel I. Capel15217.35
Mario Rossainz López261.90