Thesis supervisor: Gábor Wiener
Location of studies (in Hungarian): Számítástudományi és Információelméleti Tanszék Abbreviation of location of studies: SZIT
Description of the research topic:
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.
Further requirements: az angol nyelv közepes szintű ismerete és megfelelő gráfelméleti ismeretek
Number of students who can be accepted: 1
Deadline for application: 2019-06-14
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).
Login
