
arXiv: 1802.07177
This paper introduces an extended notion of expansion suitable for radio networks. A graph $G=(V,E)$ is called an $(��_w, ��_w)$-{wireless expander} if for every subset $S \subseteq V$ s.t. $|S|\leq ��_w \cdot |V|$, there exists a subset $S'\subseteq S$ s.t. there are at least $��_w \cdot |S|$ vertices in $V\backslash S$ adjacent in $G$ to exactly one vertex in $S'$. The main question we ask is the following: to what extent are ordinary expanders also good {wireless} expanders? We answer this question in a nearly tight manner. On the positive side, we show that any $(��, ��)$-expander with maximum degree $��$ and $��\geq 1/��$ is also a $(��_w, ��_w)$ wireless expander for $��_w = ��(��/ \log (2 \cdot \min\{��/ ��, ��\cdot ��\}))$. Thus the wireless expansion is smaller than the ordinary expansion by at most a factor logarithmic in $\min\{��/ ��, ��\cdot ��\}$, which depends on the graph \emph{average degree} rather than maximum degree; e.g., for low arboricity graphs, the wireless expansion matches the ordinary expansion up to a constant. We complement this positive result by presenting an explicit construction of a "bad" $(��, ��)$-expander for which the wireless expansion is $��_w = O(��/ \log (2 \cdot \min\{��/ ��, ��\cdot ��\})$. We also analyze the theoretical properties of wireless expanders and their connection to unique neighbor expanders, and demonstrate their applicability: Our results yield improved bounds for the {spokesmen election problem} that was introduced in the seminal paper of Chlamtac and Weinstein (1991) to devise efficient broadcasting for multihop radio networks. Our negative result yields a significantly simpler proof than that from the seminal paper of Kushilevitz and Mansour (1998) for a lower bound on the broadcast time in radio networks.
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)
FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 1 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
