témavezető: Wiener Gábor
helyszín (magyar oldal): Számítástudományi és Információelméleti Tanszék helyszín rövidítés: SZIT
A kutatási téma leírása:
A hálózatok elmélete napjaink egyik legfontosabb, legdinamikusabban fejlődő kutatási területe. Alkalmazásai rendkívül szerteágazók: nem csak az informatikában (pl. számítógéphálózatok, chipek tervezése, optikai hálózatok, számítógépes biológia, kódolás), hanem az elektronikában, a biológiában, a kémiában, sőt a szociális hálózatok (pl. Facebook, Linkedin) kapcsán a társadalomtudományokban és az üzleti életben is hasznosíthatók. Számos alkalmazás esetében bírnak nagy fontossággal a hosszú körök, utak, vagy egyéb speciális feszítőfák. A Hamilton-kör probléma NP-teljessége miatt azonban ezek megtalálására nem ismertek (és nem is várhatók) hatékony algoritmusok, sőt a vonatkozó feladatokra érdemi karakterizációk sem léteznek. Előrelépést így közelítő algoritmusoktól (és heurisztikáktól), valamint a kapcsolódó struktúrák minél pontosabb leírásától várhatunk.
A téma feldolgozása során a Hamilton-kör és Hamilton-út probléma különböző vonatkozásaival, közelítéseivel és kiterjesztéseivel foglalkozunk, mint például hypohamiltonian és hypotraceable gráfok, minimális levélszámú feszítőfák és feszítő pókok.
további elvárások: az angol nyelv közepes szintű ismerete és megfelelő gráfelméleti ismeretek
Bejelentkezés
