In this paper, we focus on graph class identification problems in the population protocol model. A graph class identification problem aims to decide whether a given communication graph is in the desired class (e.g. whether the given communication graph is a ring graph). Angluin et al. proposed graph class identification protocols with directed graphs and designated initial states under global fairness [Angluin et al., DCOSS2005]. We consider graph class identification problems for undirected graphs on various assumptions such as initial states of agents, fairness of the execution, and initial knowledge of agents. In particular, we focus on lines, rings, $k$-regular graphs, stars, trees, and bipartite graphs. With designated initial states, we propose graph class identification protocols for $k$-regular graphs, and trees under global fairness, and propose a graph class identification protocol for stars under weak fairness. Moreover, we show that, even if agents know the number of agents $n$, there is no graph class identification protocol for lines, rings, $k$-regular graphs, trees, or bipartite graphs under weak fairness. On the other hand, with arbitrary initial states, we show that there is no graph class identification protocol for lines, rings, $k$-regular graphs, stars, trees, or bipartite graphs.
翻译:在本文中,我们侧重于人口协议模型中的图表类识别问题。 图形类识别问题旨在确定某一通信图表是否属于理想类别( 例如,特定通信图表是否是一个环形图 ) 。 安格鲁因等人提议了具有定向图表和指定初始状态的图表类识别协议,以及全球公平[Angluin等人, DCOSS2005] 。 我们考虑了各种假设中非定向图表类识别问题,如代理商初始状态、执行公正性和代理商初始知识等。 特别是,我们侧重于线、 环、 美元常规图表、 恒星、 树和双方图表。 在指定的初始状态下,我们提议了美元普通图表类的图表类识别协议,以及全球公平性下的树木,并为不公平的恒星提议了一个图表类识别协议。 此外,我们表明,即使代理商知道代理商数量为1美元, 也不存在线、 环、 美元 普通图表、 树或双方图表。 在指定的初始状态上, 我们展示的是, 直方平面的图形, 。