Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Genetic Algorithms For Vertex Splitting In Dags, Matthias Mayer, Fikret ErçAl
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 …