Kim, Y;
Kumbhat, M;
Nagy, ZL;
Patkos, B;
Pokrovskiy, A;
Vizer, M;
(2015)
Identifying codes and searching with balls in graphs.
Discrete Applied Mathematics
, 193
pp. 39-47.
10.1016/j.dam.2015.03.018.
Preview |
Text
1405.7508.pdf - Accepted Version Download (380kB) | Preview |
Abstract
Given a graph and a positive integer we address the following combinatorial search theoretic problem: What is the minimum number of queries of the form “does an unknown vertex belong to the ball of radius around ?” with and that is needed to determine . We consider both the adaptive case when the th query might depend on the answers to the previous queries and the non-adaptive case when all queries must be made at once. We obtain bounds on the minimum number of queries for hypercubes, the Erdős–Rényi random graphs and graphs of bounded maximum degree.
| Type: | Article |
|---|---|
| Title: | Identifying codes and searching with balls in graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1016/j.dam.2015.03.018 |
| Publisher version: | https://doi.org/10.1016/j.dam.2015.03.018 |
| Language: | English |
| Additional information: | This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions. |
| Keywords: | Identifying codes, Combinatorial search, Hypercube, Erdős–Rényi random graph, Bounded degree graphs |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10112664 |
Archive Staff Only
 |
View Item |
