Kim, Younjin and Kumbhat, Mohit and Nagy, Zoltán Lóránt and Patkós, Balázs and Pokrovskiy, Alexey and Vizer, Máté (2015) Identifying codes and searching with balls in graphs. DISCRETE APPLIED MATHEMATICS, 193. pp. 39-47. ISSN 0166-218X
|
Text
1405.7508.pdf Available under License Creative Commons Attribution. Download (380kB) | Preview |
Abstract
Given a graph G and a positive integer R we address the following combinatorial search theoretic problem: What is the minimum number of queries of the form "does an unknown vertex v is an element of V (G) belong to the ball of radius r around u?" with u is an element of V (G) and r <= R that is needed to determine v. We consider both the adaptive case when the jth 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 Erdos-Renyi random graphs and graphs of bounded maximum degree. (C) 2015 Elsevier B.V. All rights reserved.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Graph theory; Random graphs; Graphic methods; Hypercube; Erdos-Rényi random graph; Combinatorial search; Bounded degree graphs; Identifying codes; Identifying code; |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 09 Nov 2023 14:12 |
| Last Modified: | 09 Nov 2023 14:12 |
| URI: | http://real.mtak.hu/id/eprint/179468 |
Actions (login required)
 |
Edit Item |
