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
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).
Bejelentkezés
