Testing Equality in Communication Graphs
Testing Equality in Communication Graphs
复制标题
测试通信图中的相等性
DOI：
--
复制
发表时间：
2016
影响因子：
2.5
通讯作者：
B. Sudakov
中科院分区：
文献类型：
--
作者：
N. Alon;K. Efremenko;B. Sudakov
Let <inline-formula> <tex-math notation="LaTeX">$G = (V, E)$ </tex-math></inline-formula> be a connected undirected graph with <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula> vertices. Suppose that on each vertex of the graph there is a player having an <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula>-bit string. Each player is allowed to communicate with its neighbors according to a (static) agreed communication protocol, and the players must decide, deterministically, if their inputs are all equal. What is the minimum possible total number of bits transmitted in a protocol solving this problem ? We determine this minimum up to a lower order additive term in many cases. In particular, we show that it is <inline-formula> <tex-math notation="LaTeX">$kn/2+o(n)$ </tex-math></inline-formula> for any Hamiltonian <inline-formula> <tex-math notation="LaTeX">$k$ </tex-math></inline-formula>-vertex graph, and that for any 2-edge connected graph with <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> edges containing no two adjacent vertices of degree exceeding 2 it is <inline-formula> <tex-math notation="LaTeX">$ ext {mn}/2+o(n)$ </tex-math></inline-formula>. The proofs combine graph theoretic ideas with tools from additive number theory.
