Experimental Investigation of Some Algorithms for Computing a Maximum Flow in Flow Networks,


Бакоев, Валентин (2016) Experimental Investigation of Some Algorithms for Computing a Maximum Flow in Flow Networks, Proceedings of the 3rd Virtual Multidisciplinary Conference, held at www.quaesti.com during December, 7 - 11, 2015, Zilina, Slovakia. ISSN: 2453-7144; CD ROM ISSN: 1339-5572; ISBN: 978-80-554-1170-5. DOI: 10.18638/quaesti.2015.3.1


 Here we present some investigations and results from the bachelor thesis of the second author. Some of the most popular algorithms for computing a maximum flow in a network are considered in it. Their executions on 3 groups of selected tests are examined and the corresponding running times are compared. On the basis of the experimental results some conclusions are derived. After the defense of the thesis the investigations were continued. We made a simplification of the Edmonds-Karp algorithm. The result is an approximate algorithm, which has better time and space complexities compared to the usual Edmonds-Karp algorithm. Finally by testing different combinations of data structures and heuristics we are able to derive some general conclusion about the different approaches for implementing the algorithms.
  Доклад
 Flow networks, Ford-Fulkerson method, Edmonds-Karp algorithm, Push-relabel algorithm, Experimental evaluation


Природни науки, математика и информатика Информатика и компютърни науки
Природни науки, математика и информатика

Natural sciences, mathematics and informatics
Natural sciences, mathematics and informatics Informatics and Computer Science

 Издадено
  14328
 Валентин Бакоев

Научният архив поддържа инициативата за отворен достъп OAI 2.0 с начален адрес: http://da.uni-vt.bg/oai2/