Thesis supervisor: Gyula Y. Katona
Location of studies (in Hungarian): BME VIK Számítástudományi és Információelméleti Tanszék Abbreviation of location of studies: BME
Description of the research topic:
A gráf kövezés (pebbling) problémájával 20 éve kezdtek foglalkozni, eredetileg egy számelméleti probléma kapcsán merült fel. Azóta több mint 100 cikk foglalkozik a témával. A kövezéssel kapcsolatosan többféle gráfparamétert lehet definiálni. Ezek meghatározása általában NP-nehéz, de bizonyos gráfosztályok esetében adható rájuk zárt formula.
A gráf kövezés egy kiterjesztett változata a murvázás (rubbling). Ez egy eddig kevésbé felfedezett terület, de már itt is vannak érdekes eredmények. Sok esetben hasonlóak a kövezés esetén kapott eredményekhez, de érdekes különbségek is vannak.
A kutatás során a témakör nyitott problémáival foglalkozna a jelölt. Egy érdekes irány lehet, hogy milyen bővebb gráfosztályok esetén van polinomiális algoritmus a kövezési illetve murvázási számok meghatározására
Required language skills: angol Further requirements: Gráfelmélet, algoritmuselmélet, angol nyelv.