Témakiírások
Azonosító kódok gráfokban
témakiírás címe
Azonosító kódok gráfokban
intézmény
doktori iskola
témakiíró
társtémakiíró
tudományág
témakiírás 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.
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 fő
helyszín
Pannon Egyetem, Rendszer és Számítástudományi Tsz.
jelentkezési határidő
2017-10-30