Ritka (rész)gráfok keresése és generálása

Témavezető: Madarasi Péter
ELTE TTK, Operációkutatási Tsz.
email: madarasip@staff.elte.hu

Projekt leírás

A projekt célja a kis (k,l)-ritka részgráfok legenerálása [1], valamint a legsúlyosabb (k,l)-ritka részgráf keresésére vonatkozó algoritmusok [2] felgyorsítása. A témakör egyik nyitott kérdése, hogy hogyan lehet az utóbbi feladatot o(|V|3) lépésben megoldani sűrű gráfokon. A kis gráfok legenerálásához nagyon sok kicsi gráf közül hatékonyan ki kell tudnunk szűrni a (k,l)-ritkákat. A kihívás mindkét esetben a hatékony adatszerkezetek megtervezésében rejlik.

Előfeltételek

Gráfelméleti és algoritmuselméleti alapok, programozói tapasztalat C++ nyelven.

Hivatkozások

[1] McKay, B.D., 1998. Isomorph-free exhaustive generation. Journal of Algorithms, 26(2), pp.306-324.

[2] Lee, A. and Streinu, I., 2008. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8), pp.1425-1437.

Hallgató