Name
Abstract | ||
|---|---|---|
In this paper we deal with codes identifying sets of vertices in random graphs, that is l-identifying codes. These codes enable us to detect sets of faulty processors in a multiprocessor system, assuming that the maximum number of faulty processors is bounded by a fixed constant e. The 1-identifying codes or simply identifying codes are of special interest. For random graphs we use the model g(n,p), in which each one of the ((n)(2)) possible edges exists with probability p. We give upper and lower bounds on the minimum cardinality of an l-identifying code in a random graph, as well as threshold functions for the property of admitting such a code. We derive existence results from probabilistic constructions. A connection between identifying codes and superimposed codes is also established. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/ISIT.2005.1523586 | 2005 IEEE International Symposium on Information Theory (ISIT), Vols 1 and 2 |
Keywords | Field | DocType |
random graphs,upper and lower bounds,codes,random graph,graph theory,set theory | Discrete mathematics,Hamming code,Online codes,Combinatorics,Concatenated error correction code,Luby transform code,Computer science,Block code,Expander code,Reed–Muller code,Linear code | Conference |
Citations | PageRank | References |
2 | 0.39 | 3 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alan M. Frieze | 1 | 4837 | 787.00 |
| Ryan Martin | 2 | 144 | 14.43 |
| Julien Moncel | 3 | 191 | 17.33 |
| Miklós Ruszinko | 4 | 8 | 1.30 |
| Cliff Smyth | 5 | 64 | 4.92 |