témavezető: Csaba Béla
helyszín (magyar oldal): SZTE Matematika- és Számítástudományok Doktori Iskola helyszín rövidítés: MatDI
A kutatási téma leírása:
A pakolási alapfeladat két gráf esetén annak eldöntése, egy H gráf részgráfja-e egy G gráfnak. Ez a gráfelmélet egy központi, nagyon aktívan kutatott kérdésköre. A pakolási problémáknak sok alkalmazása van kombinatorikában, geometriában, számítástudományban, de a matematika egyéb területein is. A fenti tartalmazási kérdés sokszor NP-teljes probléma. Ez azt jelenti, hogy általában elégséges feltételt keresünk, mely biztosítja a tartalmazást. Így extremális gráfelméleti kérdésekhez jutunk. Különösen fontos fák, korlátos fokú részgráfok keresése sűrű vagy véletlen gráfokban, melyekre valamilyen strukturális kikötést teszünk fel. A cél a fenti típusú problémák vizsgálata, konkrét problémák megoldása és ha szükséges új, általános módszerek kifejlesztése is.