Thesis supervisor: Zsolt Tuza
co-supervisor: Csilla Bujtás
Location of studies (in Hungarian): University of Pannonia, Department of Computer Science and Systems Technology Abbreviation of location of studies: PE
Description of the research topic:
The problem originates from the fault diagnosis in multiprocessor systems where testers must be positioned so that the faults can be exactly localized by considering only which testers detect fault in their neighborhoods.
Formally, given a graph G, a C subset of V(G) is called identifying code if it intersects the neighborhoods of the vertices in pairwise different nonempty sets. The goal is to find an
identifying code of minimum cardinality in a (twin-free) graph. Inspired by theoretical aspects and different types of applications, further variants of this definition were introduced.
The aim of the research is to estimate the minimum size of an identifying code and to develop exact/approximation algorithms under conditions imposed on the structure of the network.
Preliminary results can be found in the following publications:
[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.
Login
