2015/08/18 by Fabian Fuchs, Fabian B. Fuchs, Fuchs, Fabian +2
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Cooperative Communication and Network Coding #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1508.04278
arxiv created 2015/08/18 · openalex publication_date 2015/08/18 · arxiv updated 2015/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
One of the most fundamental problems in wireless networks is to achieve high throughput. Fractional Connected Dominating Set (FCDS) Packings can achieve a throughput of Θ(k/log n) messages for networks with node connectivity k, which is optimal regarding routing-based message transmission. FCDS were proposed by Censor-Hillel et al. [SODA'14,PODC'14] and are a natural generalization to Connected Dominating Sets (CDS), allowing each node to participate with a fraction of its weight in multiple FCDS. Thus, Ω(k) co-existing transmission backbones are established, taking full advantage of the networks connectivity. We propose a modified distributed algorithm that improves upon previous algorithms for kΔ∈ o(min\(n log n)/(k) ,D,√(n log n) log^* n\log n), where Δ is the maximum node degree, D the diameter and n the number of nodes in the network. We achieve this by explicitly computing connections between tentative dominating sets.