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

Viktor Arkhipov, Maxim Buzdalov, A. A. Shalyto

Research output: Chapter in Book/Report/Conference proceedingConference Proceeding (Non-Journal item)

7 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationICMLA '13
Subtitle of host publicationProceedings of the 2013 12th International Conference on Machine Learning and Applications
PublisherIEEE Press
Pages108-111
Number of pages4
Volume2
ISBN (Electronic)978-0-7695-5144-9
DOIs
Publication statusPublished - 04 Dec 2013
Externally publishedYes

Fingerprint

Dive into the research topics of 'Worst-Case Execution Time Test Generation for Augmenting Path Maximum Flow Algorithms Using Genetic Algorithms'. Together they form a unique fingerprint.

Cite this