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
felvehető hallgatók száma: 1
Jelentkezési határidő: 2018-07-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).