We show how to construct an overlay network of constant degree and diameter $O(\log n)$ in time $O(\log n)$ starting from an arbitrary weakly connected graph. We assume a synchronous communication network in which nodes can send messages to nodes they know the identifier of, and new connections can be established by sending node identifiers. If the initial network's graph is weakly connected and has constant degree, then our algorithm constructs the desired topology with each node sending and receiving only $O(\log n)$ messages in each round in time $O(\log n)$, w.h.p., which beats the currently best $O(\log^{3/2} n)$ time algorithm of [G\"otte et al., SIROCCO'19]. Since the problem cannot be solved faster than by using pointer jumping for $O(\log n)$ rounds (which would even require each node to communicate $\Omega(n)$ bits), our algorithm is asymptotically optimal. We achieve this speedup by using short random walks to repeatedly establish random connections between the nodes that quickly reduce the conductance of the graph using an observation of [Kwok and Lau, APPROX'14]. Additionally, we show how our algorithm can be used to efficiently solve graph problems in \emph{hybrid networks} [Augustine et al., SODA'20]. Motivated by the idea that nodes possess two different modes of communication, we assume that communication of the \emph{initial} edges is unrestricted, whereas only polylogarithmically many messages can be communicated over edges that have been established throughout an algorithm's execution. For an (undirected) graph $G$ with arbitrary degree, we show how to compute connected components, a spanning tree, and biconnected components in time $O(\log n)$, w.h.p. Furthermore, we show how to compute an MIS in time $O(\log d + \log \log n)$, w.h.p., where $d$ is the initial degree of $G$.


翻译:我们展示如何构建一个以恒定度和直径为no( log n) 的覆盖网络, 时间为$O( log n) 美元, 时间为$O( log n) 美元。 我们假设一个同步的通信网络, 节点可以将信息发送到节点中, 并可以通过发送节点标识建立新的连接。 如果初始网络的图形连接不力, 并且具有恒定度, 那么我们的算法会构建理想的表层, 每个节点发送和接收的只有$O( log n) 美元, 时间为$( log n) 美元, w. h. p. 美元, 这比当前最佳的 O( log log n) 通信网络同步化 。 我们通过快速的 O( log ) 14 14 美元, 时间算得比 点跳过 。

0
下载
关闭预览

相关内容

【IJCAJ 2020】多通道神经网络 Multi-Channel Graph Neural Networks
专知会员服务
25+阅读 · 2020年7月19日
【清华大学】图随机神经网络,Graph Random Neural Networks
专知会员服务
154+阅读 · 2020年5月26日
神经网络的拓扑结构,TOPOLOGY OF DEEP NEURAL NETWORKS
专知会员服务
31+阅读 · 2020年4月15日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
一文读懂依存句法分析
AINLP
16+阅读 · 2019年4月28日
目标检测中的Consistent Optimization
极市平台
6+阅读 · 2019年4月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【音乐】Attention
英语演讲视频每日一推
3+阅读 · 2017年8月22日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Arxiv
0+阅读 · 2020年10月30日
Arxiv
0+阅读 · 2020年10月29日
Arxiv
0+阅读 · 2020年10月18日
VIP会员
相关资讯
图机器学习 2.2-2.4 Properties of Networks, Random Graph
图与推荐
10+阅读 · 2020年3月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
一文读懂依存句法分析
AINLP
16+阅读 · 2019年4月28日
目标检测中的Consistent Optimization
极市平台
6+阅读 · 2019年4月23日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【音乐】Attention
英语演讲视频每日一推
3+阅读 · 2017年8月22日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员