Physical Sciences and Mathematics Commons^™

Genetic Algorithms For Vertex Splitting In Dags, Matthias Mayer, Fikret ErçAl

Computer Science Technical Reports

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 …