= Maximális folyam algoritmusok =

A klasszikus maximális folyam problémára kidolgozott új algoritmusok hatékony implementálása és összehasonlító elemzése. 

== Háttér ==

A maximális folyam feladat egy alapvető optimalizálási probléma, amelynek megoldására számtalan különféle algoritmus született. Ezek közül néhány már implementálva van a LEMON-ban, köztük az egyik leghatékonyabb, a preflow push-relabel algoritmus is. Ugyanakkor vannak újabb algoritmusok is, amelyeket a gyakrolatban igen hatékonynak találtak. Például:
  * [http://www.cs.tau.ac.il/~sagihed/dsw10a/goldberg.pdf Goldberg. The Partial Augment–Relabel Algorithm for the Maximum Flow Problem, 2008.] Ez a preflow push-relabel algoritmusnak egy módosított változata, amely a gyakorlatban hatékonyabbnak, robusztusabbnak bizonyult.
  * [http://pubsonline.informs.org/doi/abs/10.1287/opre.1080.0572 Chandran, Hochbaum. A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem, 2009.]
  * [http://dl.acm.org/citation.cfm?id=2414855 Hochbaum, Orlin. Simplifications and speedups of the pseudoflow algorithm, 2013.]
  * [http://research.microsoft.com/pubs/150437/ibfs-proc.pdf Goldberg et al. Maximum Flows by Incremental Breadth-First Search, 2011.]

Az algoritmusok teszteléséhez jól használható gráfgenerátorokat lehet találni pl. [ftp://dimacs.rutgers.edu/pub/netflow/generators/network/ itt]. Computer vision alkalmazásokból származó nagyon nagy méretű tesztadatokat pedig le lehet tölteni [http://vision.csd.uwo.ca/data/maxflow/ innen].

== Feladat ==

A feladat néhány új, ígéretesnek tűnő maximális folyam algoritmus implementálása és alapos összehasonlító elemzése különböző gráfokon. Továbbá érdemes lenne a már meglévő preflow push-relabel implementáció javítási lehetőségeit is megvizsgálni (pl. next arc heurisztika alkalmazása, meglévő heurisztikák paramétereinek felülvizsgálata stb.).

A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.

== Előfeltételek ==

 - C++ programozási nyelv ismerete
 - alapvető gráfelméleti ismeretek 
 - angol nyelvismeret