Thesis supervisor: Béla Csaba
Location of studies (in Hungarian): SZTE Matematika- és Számítástudományok Doktori Iskola Abbreviation of location of studies: MatDI
Description of the research topic:
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.
Login
