TY - GEN
T1 - Comparative study of representations in the maximum flow test generation problem
AU - Mironovich, Vladimir
AU - Buzdalov, Maxim
AU - Parfenov, Vladimir
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Evolutionary algorithms
KW - Hard test generation
KW - Maximum flow
KW - Representations
UR - http://www.scopus.com/inward/record.url?scp=85014963996&partnerID=8YFLogxK
M3 - Conference Proceeding (Non-Journal item)
AN - SCOPUS:85014963996
T3 - Mendel
SP - 67
EP - 72
BT - MENDEL 2016 - 22nd International Conference on Soft Computing
A2 - Radek, Matousek
PB - Brno University of Technology
T2 - 22nd 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
Y2 - 8 June 2016 through 10 June 2016
ER -