























In research on distributed local algorithms it is commonly assumed that each vertex has a unique identifier in the entire graph. However, it turns out that in case of certain classes of graphs (for example not lift-closed bounded degree graphs) identifiers are unnecessary and only a port ordering is needed. One of the open issues was whether identifiers are essential in planar graphs. In this paper, we answer this question and we propose an algorithm which returns constant approximation of the MDS problem in CONGEST model. The algorithm doesn't use any additional information about the structure of the graph and the nodes don't have unique identifiers. We hope that this paper will be very helpful as a hint for further comparisons of the unique identifier model and the model with only a port numbering in other classes of graphs.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。