# Amplified Pruning and Path Selectors for Deterministic Radio Gossiping

Preprint · Qin Xin

- Archive id: arxiv:2610.28930
- Published: 2026-10-20
- arXiv: https://arxiv.org/abs/2610.28930
- Source URL: https://arxiv.org/abs/2610.28930
- PDF: https://arxiv.org/pdf/2610.28930
- Provenance: arxiv

## Abstract

We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $\[N\]$, where $N=n^{\\mathcal O(1)}$. Messages are unrestricted and collision detection is unavailable. Our neighborhood-clearing procedure reuses an elected receiver to secure its entire closed in-neighborhood in $\\mathcal O(n\\log^2n\\log\\log n)$ rounds. Charging each distinct closed neighborhood once yields $\\mathcal O(m\\log^2n\\log\\log n)$ rounds under an explicit degree-concentration condition, for every polynomial identifier range. A complementary adaptive-pruning procedure combines quadratic contraction with completion sensitive to the number of unsecured sources. If $a\\ge1$ sources remain at completion entry, permutation selectors reduce the balanced completion budget by a factor of $\\log^{2/3}(a+1)$ relative to interleaved path selectors. A geometric execution attains $\\widetilde{\\mathcal O}(k^2+nτ+\\min\\{u^2,(nu)^{2/3}\\})$ for a path cover of scale $k$, weight $τ$, and $u$ exceptions. For directed graphs with common in- and out-degree $Δ$, the portfolio achieves $\\widetilde{\\mathcal O}(\\min\\{n\\sqrtΔ,n^2/Δ\\})$. Every graph also admits $\\widetilde{\\mathcal O}(\\min\\{n^{4/3},N+(mn)^{3/5}\\})$ rounds. Only $n,N$ are inputs; degrees, covers, and structural constants are used solely in the analysis. The unrestricted polynomial-identifier density extension remains open.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.