Worst-Case Execution Time Test Generation for Augmenting Path Maximum Flow Algorithms using Genetic Algorithms

Worst-case execution time tests can be tricky to create for various computer science algorithms. To reduce the amount of human effort, authors suggest using search-based optimization techniques, such as genetic algorithms. This paper addresses difficult test generation for several maximum flow algorithms from the augmenting path family. The presented results show that the genetic approach is reasonably good for the well-studied algorithms and superior for the capacity scaling algorithms. Moreover, tests which are generated against one algorithm seem to be hard for other algorithms of this family.