Irányítatlan gráfok minimális vágásainak keresése fontos elméleti és
gyakorlati problémákkal függ össze. Jól ismertek minimális vágást kereső,
hatékony algoritmusok (Ford-Fulkerson, Karger, Nagamochi-Ibaraki), melyek segítségével adott tulajdonságú minimális vágás megkereshető. Ugyancsak jól ismert az irányítatlan gráf globális minimális vágásainak struktúrája, mely egy ún. kaktuszgráffal írható le, ám számos alkalmazás szempontjából hasznos lenne egy olyan leíró struktúra, amely az irányítatlan gráf minden (u,v) csúcspárjához leírja az összes minimális uv-szeparáló vágást. Ezen struktúra keresése és lehetséges elméleti alkalmazásai a kutatás fő kérdései.
előírt nyelvtudás: angol felvehető hallgatók száma: 1
Jelentkezési határidő: 2024-05-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Bejelentkezés
