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.
Hivatkozások
[1] Lee, A. and Streinu, I., 2008. Pebble game algorithms and sparse graphs. Discrete Mathematics, 308(8), pp.1425-1437.