Comparative study of representations in the maximum flow test generation problem

Vladimir Mironovich, Maxim Buzdalov, Vladimir Parfenov

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

Abstract

We consider the problem of generating, with the use of evolutionary algorithms, hard tests (that is, tests that maximize the running time) for the algorithms solving the well-known maximum flow problem. The main aim of this paper is to study the impact of the representation of the graph, in which the maximum flow is constructed. We consider three representations: the list of edges, the adjacency matrix, and the adjacency matrix with access to individual bits of capacities. Our study suggests that the list of edges is the best representation among the considered ones.

Original languageEnglish
Title of host publicationMENDEL 2016 - 22nd International Conference on Soft Computing
Subtitle of host publicationEvolutionary Computation, Genetic Programming, Swarm Intelligence, Fuzzy Logic, Neural Networks, Chaos, Bayesian Methods, Intelligent Image Processing, Bio-Inspired Robotics
EditorsMatousek Radek
PublisherBrno University of Technology
Pages67-72
Number of pages6
ISBN (Electronic)9788021453654
Publication statusPublished - 2016
Externally publishedYes
Event22nd International Conference on Soft Computing: Evolutionary Computation, Genetic Programming, Swarm Intelligence, Fuzzy Logic, Neural Networks, Chaos, Bayesian Methods, Intelligent Image Processing, Bio-Inspired Robotics, MENDEL 2016 - Brno, Czech Republic
Duration: 08 Jun 201610 Jun 2016

Publication series

NameMendel
ISSN (Print)1803-3814

Conference

Conference22nd International Conference on Soft Computing: Evolutionary Computation, Genetic Programming, Swarm Intelligence, Fuzzy Logic, Neural Networks, Chaos, Bayesian Methods, Intelligent Image Processing, Bio-Inspired Robotics, MENDEL 2016
Country/TerritoryCzech Republic
CityBrno
Period08 Jun 201610 Jun 2016

Keywords

  • Evolutionary algorithms
  • Hard test generation
  • Maximum flow
  • Representations

Fingerprint

Dive into the research topics of 'Comparative study of representations in the maximum flow test generation problem'. Together they form a unique fingerprint.

Cite this