Graph labelings derived from models in distributed omputing
Graph labelings derived from models in distributed omputing
复制标题
从分布式计算模型派生的图标签
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
D. Paulusma
中科院分区：
文献类型：
--
作者：
emie Chalopin;D. Paulusma
阿布斯特拉湾本文讨论了11种著名的分布式计算的基本模型：4种以端口号（非）确定性区分的消息传递模型和7种分层的局部计算模型。在每一个模型中，我们研究了在给定的网络上，领导者的选择和/或命名问题是否能被解决的决策问题的计算复杂性。我们已经知道这个问题对于两个模型是多项式时间可解的，而对于另一个模型是o-NP完全的。在这里，我们解决了计算的复杂性，其余8个问题，显示o-NP-完全。六个模型的结果和已知的o-NP-完备性结果来自于图标号的一个更一般的结果
Abstra t. We dis uss eleven well-known basi models of distributed omputing: four message-passing models that di(cid:11)er by the (non-)existen e of port-numbers and a hierar hy of seven lo al omputations models. In ea h of these models, we study the omputational omplexity of the de ision problem whether the leader ele tion and/or naming problem an be solved on a given network. It is already known that this problem is solvable in polynomial time for two models and o-NP-omplete for another one. Here, we settle the omputational omplexity for the remaining eight problems by showing o-NP-ompleteness. The results for six models and the already known o-NP-ompleteness result follow from a more general result on graph labelings