http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.
변환된 중국어를 복사하여 사용하시면 됩니다.
Identifying codes and searching with balls in graphs
Kim, Y.,Kumbhat, M.,Nagy, Z.L.,Patkos, B.,Pokrovskiy, A.,Vizer, M. North Holland ; Elsevier Science Ltd 2015 Discrete Applied Mathematics Vol.193 No.-
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@?V(G) belong to the ball of radius r around u?'' with u@?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.