A maximális folyam algoritmusok időben változó hálózatokban

Témavezető:	Tapolcai János
	BME VIK TMIT
email:	tapolcai@tmit.bme.hu

Projekt leírás

Városi környezetekben intenzíven vizsgált terület azoknak a mobil hálózatoknak a kialakítása, ahol a felhasználók mozgó eszközök, mint drónok, gépjárművek, alacsony pályán keringő műholdak stb. segítségével kommunikálnak. Ebben az esetben a kihívás az alábbi: Adott egy gráf, melynek éleinek kapacitása időben változik (ezt hívjuk időben változó hálózatnak), továbbá van egy forrás- és egy nyelőpont. A gráf minden csomópontjához ismerjük a buffer méretét, ami a tárolható információ maximális mennyiségét jelöli. A cél az, hogy kiszámoljuk, mennyi idő alatt juthat el egy adott mennyiségű adat a forrástól a nyelőig. Ehhez a klasszikus megoldás, hogy egy maximális folyamot kell számolnak egy hatalmas gráfon. A gráf az időben változó hálózat “időszeleteiből” áll. Így ahhoz, hogy a számítás kellően pontos legyen, ez a gráf óriási lenne (pár ezer mobil eszköz és pár ezer időszelet több tízmillió pontos gráfot eredményezne). Ennek kezelése egy olyan algoritmikus kihívás, ami jelenleg sok alkalmazás megvalósíthatóságának az akadálya. A hallgatóval ennek a problémakörnek a részleteit vizsgálnánk, és egy konkrét egyszerűsítés alapján próbálnánk megoldani a kihívást. Azt használnánk ki, hogy a gráf az egymás utáni időszeletekben nem tér el nagyon.

Előfeltételek

Gráfalgortimusok, analízis, algoritmusok hatékony (c/c++) implemenetációja, angol nyelv

Hivatkozások

[1] Skutella, Martin. "An introduction to network flows over time." Research Trends in Combinatorial Optimization: Bonn 2008, pp. 451-482

[2] Vernet M, Drozdowski M, Pigné Y, Sanlaville E. A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs. Discrete Applied Mathematics. 2021 Jun 15;296:203-16.