Abstract
Directed Acyclic Graphs (DGAs) are often used to model circuits and networks. The path length in such DAGs represents circuit or network delays. In the vertex splitting problem, the objective is to determine a minimum number of vertices from the graph to split such that the resulting graph has no path of length greater than a given maximum delay δ. The problem has been proven to be NP-hard. A sequential Genetic Algorithm has been developed to solve the DAG Vertex Splitting Problem. Unlike a standard Genetic Algorithm, this approach uses a variable chromosome length to represent the vertices that split the graph and a dynamic population size. A parallel version of the sequential Genetic Algorithm has been developed. It uses a fully distributed scheme to assign different string lengths to processors. A ring exchange method is used in order to exchange ’’good” individuals between processors. Almost linear speed-up and two cases of super linear speed-up are reported.
Recommended Citation
Mayer, Matthias, "Parallel Genetic Algorithm for the DAG Vertex Splitting Problem" (1993). Computer Science Technical Reports. 43.
https://scholarsmine.mst.edu/comsci_techreports/43
Department(s)
Computer Science
Keywords and Phrases
Parallel Genetic Algorithm; Variable string length; Dynamic population size; Vertex splitting
Report Number
CSC-93-21
Document Type
Technical Report
Document Version
Final Version
File Type
text
Language(s)
English
Rights
© 1993 University of Missouri--Rolla, All rights reserved.
Publication Date
23 Jul 1993
