Bejelentkezés
 Fórum
 
 
Témakiírás
 
Wiener Gábor
Gráfok hosszú körei és útjai

TÉMAKIÍRÁS

Intézmény: Budapesti Műszaki és Gazdaságtudományi Egyetem
informatikai tudományok
Informatikai Tudományok Doktori Iskola

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ő: 2019-06-14


2019. IX. 13.
ODT ülés
Az ODT következő ülésére 2019. november 22-én 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 2.2358 ( 2017. X. 31. )