A Pebble game és kapcsolódó algoritmusok implementá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 legsúlyosabb (k,l)-ritka részgráf keresésre vonatkozó Pebble game algoritmusok [1] felgyorsítása és implementálása. Az témakör egyik nyitott kérdése, hogy hogyan lehet az előbbi feladatot o(|V|3) lépésben megoldani sűrű gráfokon. Ezen kívül implementálunk 1) legsúlyosabb k diszjunkt feszítőfát, 2) k erdővel való fedést, 3) k diszjunkt kifenyőt és 4) k diszjunkt kifenyvessel való fedést kereső algoritmusokat is, amelyek szorosan kapcsolódnak a (k,l)-ritka részgráfot kereső algoritmushoz.
Előfeltételek
Elvárás a programozói tapasztalat C++ nyelven, a gráfelméleti alapok és az angol szakmai nyelv ismerete.
Hivatkozások
[1] Lee, A. and Streinu, I., 2008. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8), pp.1425-1437.