Wireless Expanders
share
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 ⊆ V s.t. |S|≤α_w · |V|, there exists a subset S'⊆ S s.t. there are at least β_w · |S| vertices in V 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 β≥ 1/Δ is also a (α_w, β_w) wireless expander for β_w = Ω(β / (2 ·{Δ / β, Δ·β})). Thus the wireless expansion is smaller than the ordinary expansion by at most a factor logarithmic in {Δ / β, Δ·β}, which depends on the graph 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(β / (2 ·{Δ / β, Δ·β}). 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.
READ FULL TEXT