Thesis supervisor: Tamás Fleiner
Location of studies (in Hungarian): BME VIK SZIT Abbreviation of location of studies: BME
Description of the research topic:
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.
Required language skills: English Number of students who can be accepted: 1