In the study of radio networks, the tasks of broadcasting (propagating a message throughout the network) and leader election (having the network agree on a node to designate `leader') are two of the most fundamental global problems, and have a long history of work devoted to them. This work has two divergent strands: some works focus on exploiting the geometric properties of wireless networks based in physical space, while others consider general graphs. Algorithmic results in each of these avenues have often used quite different techniques, and produced bounds using incomparable parametrizations. In this work, we unite the study of general-graph and geometric-based radio networks, by adapting the broadcast and leader election algorithm of Czumaj and Davies (JACM '21) to achieve a running-time parametrized by the independence number of the network (i.e., the size of the maximum independent set). This parametrization preserves the running time on general graphs, matching the best known, but also improves running times to near-optimality across a wide range of geometric-based graph classes. As part of this algorithm, we also provide the first algorithm for computing a maximal independent set in general-graph radio networks. This algorithm runs in $O(\log^3 n)$ time-steps, only a $\log n$ factor away from the $\Omega(\log^2 n)$ lower bound.


翻译:在无线电网络研究中,广播(在整个网络中传播消息)和领导者选举(使网络就指定“领导者”的节点达成一致)是最基本的两个全局问题,并已经有长期的研究。这项工作有两种分歧方向:一些研究关注利用物理空间中的无线电网络的几何属性,而其他研究则考虑一般图。这些方法的算法结果通常使用非常不同的技术,并使用不可比较的参数化来产生界限。在这项工作中,我们将一般图和基于几何的广播网络的研究合并,通过将Czumaj和Davies(JACM'21)的广播和领导者选举算法适用于独立数的参数化来实现。这种参数化保留了一般图的运行时间,与最佳已知的相匹配,但也将广泛的基于几何的图类的运行时间提高到接近最优。作为该算法的一部分,我们还提供了第一个能够在一般图无线电网络中计算最大独立集的算法。该算法在$O(\log^3 n)$的时间步骤内运行,仅相当于$\Omega(\log^2 n)$的下界,相差不到一倍的因子。

0
下载
关闭预览

相关内容

专知会员服务
50+阅读 · 2020年12月14日
【NeurIPS2020】点针图网络,Pointer Graph Networks
专知会员服务
39+阅读 · 2020年9月27日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
八篇NeurIPS 2019【图神经网络(GNN)】相关论文
专知会员服务
43+阅读 · 2020年1月10日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
【Code】GraphSAGE 源码解析
AINLP
29+阅读 · 2020年6月22日
深度卷积神经网络中的降采样
极市平台
12+阅读 · 2019年5月24日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Arxiv
12+阅读 · 2022年11月21日
Arxiv
23+阅读 · 2018年10月1日
VIP会员
相关VIP内容
专知会员服务
50+阅读 · 2020年12月14日
【NeurIPS2020】点针图网络,Pointer Graph Networks
专知会员服务
39+阅读 · 2020年9月27日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
八篇NeurIPS 2019【图神经网络(GNN)】相关论文
专知会员服务
43+阅读 · 2020年1月10日
相关基金
国家自然科学基金
1+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员