Bejelentkezés
 Fórum
 
 
Témakiírás
 
Bujtás Csilla
Tuza Zsolt
Azonosító kódok gráfokban

TÉMAKIÍRÁS

Intézmény: Pannon Egyetem
informatikai tudományok
Informatikai Tudományok Doktori Iskola

témavezető: Tuza Zsolt
társ-témavezető: Bujtás Csilla
helyszín (magyar oldal): Pannon Egyetem, Rendszer és Számítástudományi Tsz.
helyszín rövidítés: PE


A kutatási téma leírása:

A probléma a multiprocesszor hálózatok felügyeletével kapcsolatban merült fel először. Itt úgy kell tesztereket elhelyezni, hogy egy esetleges meghibásodás helye pontosan azonosítható legyen pusztán az alapján, hogy mely teszterek érzékelnek hibát a környezetükben.

Formálisan definiálva, a G gráfban egy C részhalmaza V(G)-nek csúcshalmazt azonosító kódnak nevezünk, ha a csúcsok környezeteit páronként különböző nemüres halmazokban metszi. Adott gráf esetén a cél egy minél kisebb méretű azonosító kód meghatározása. Az azonosító kódok további fajtáit is széles körben vizsgálják, részben elméleti megfontolásokhoz, részben pedig más típusú
alkalmazásokhoz kapcsolódóan.

A kutatás célja az azonosító kódok minimális méretének becslése különböző paraméterek függvényében, valamint pontos és közelítő algoritmusok tervezése adott gráfosztályokra.

A kutatási téma előzményei az alábbi közleményekben találhatóak:

[1] M.G. Karpovsky, K. Chakrabarty, L.B. Levitin, On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, 44 (1998), 599–611.
[2] I. Charon, O. Hudry, A. Lobstein, Minimizing the size of an identifying or locating-dominating code in a graph is NP-hard. Theoretical Computer Science, 290 (2003), 2109–2120.
[3] F. Foucaud, G. Perarnau, Bounds for identifying codes in terms of degree parameters. Electronic Journal of Combinatorics, 19 (2012), #P32.

felvehető hallgatók száma: 1

Jelentkezési határidő: 2018-06-22


2019. I. 10.
ODT ülés
Az ODT következő ülésére 2019. február 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. )