Abstract
Directed Acyclic Graphs are often used to model circuits and networks. The path length in such Directed Acyclic Graphs 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 δ. The problem has been proven to be NP-hard. A Genetic Algorithm is used to solve the DAG Vertex Splitting Problem. This approach uses a variable string length to represent the vertices that split the graph and a dynamic population size. The focus of this paper is the comparison of two methods to reduce the string length and of two stepping methods to explore the search space. Experimental results have shown that the multiple binary stepping method outperforms the linear stepping method in yielding better solutions.
Recommended Citation
Mayer, Matthias and Erçal, Fikret, "Genetic Algorithms for Vertex Splitting in DAGs" (1993). Computer Science Technical Reports. 25.
https://scholarsmine.mst.edu/comsci_techreports/25
Department(s)
Computer Science
Keywords and Phrases
Directed Acyclic Graph; Vertex Splitting; Genetic Algorithms; Variable String Length; Dynamic Population Size; NP-Hard
Report Number
CSC-93-02
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
29 Jan 1993
