We show that any algorithm that solves the sinkless orientation problem in the supported LOCAL model requires $\Omega(\log n)$ rounds, and this is tight. The supported LOCAL is at least as strong as the usual LOCAL model, and as a corollary this also gives a new, short and elementary proof that shows that the round complexity of the sinkless orientation problem in the deterministic LOCAL model is $\Omega(\log n)$.
翻译：我们显示,任何解决支持的 LOCAL 模型中无沉没方向问题的算法都需要$\ Omega (\log n) 圆($\ log n) 圆圆,而且这个回合很紧。 得到支持的 LOCAL 至少和通常的 LOCOL 模型一样强大, 作为推论,这也提供了一个新的、简短和基本的证据,表明确定性的 LOCAL 模型中无沉没方向问题的轮复杂程度是$\ Omega (\log n) 。
相关内容
ACM/IEEE第23届模型驱动工程语言和系统国际会议，是模型驱动软件和系统工程的首要会议系列，由ACM-SIGSOFT和IEEE-TCSE支持组织。自1998年以来，模型涵盖了建模的各个方面，从语言和方法到工具和应用程序。模特的参加者来自不同的背景，包括研究人员、学者、工程师和工业专业人士。MODELS 2019是一个论坛，参与者可以围绕建模和模型驱动的软件和系统交流前沿研究成果和创新实践经验。今年的版本将为建模社区提供进一步推进建模基础的机会，并在网络物理系统、嵌入式系统、社会技术系统、云计算、大数据、机器学习、安全、开源等新兴领域提出建模的创新应用以及可持续性。
官网链接：http://www.modelsconference.org/
相关VIP内容
相关资讯
微信扫码咨询专知VIP会员