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.