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.
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.