On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
<|reference_start|>On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols: Selective families of sets, or selectors, are combinatorial tools used to "isolate" individual members of sets from some set family. Given a set $X$ and an element $x\in X$, to isolate $x$ from $X$, at least one of the sets in the selector must intersect $X$ on exactly $x$. We study (k,N)-permutation selectors which have the property that they can isolate each element of each $k$-element subset of $\{0,1,...,N-1\}$ in each possible order. These selectors can be used in protocols for ad-hoc radio networks to more efficiently disseminate information along multiple hops. In 2004, Gasieniec, Radzik and Xin gave a construction of a (k,N)-permutation selector of size $O(k^2\log^3 N)$. This paper improves this by providing a probabilistic construction of a (k,N)-permutation selector of size $O(k^2\log N)$. Remarkably, this matches the asymptotic bound for standard strong (k,N)-selectors, that isolate each element of each set of size $k$, but with no restriction on the order. We then show that the use of our (k,N)-permutation selector improves the best running time for gossiping in ad-hoc radio networks by a poly-logarithmic factor.<|reference_end|>
@article{kuschner2024on,
    title={On Permutation Selectors and their Applications in Ad-Hoc Radio Networks
  Protocols},
    author={Jordan Kuschner, Yugarshi Shashwat, Sarthak Yadav, and Marek Chrobak},
    journal={arXiv preprint arXiv:2402.10783},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.10783},
    primaryClass={cs.DS cs.CC}
}