.png){kind=icon}
返回
Complete graph identification in population protocols
.png){kind=icon}
PRE
AI
DOI：10.1016/j.tcs.2026.115908.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们考虑人口协议模型，其中不可区分的状态机（称为智能体）在成对通信。通信图指定了智能体对之间的潜在交互（即通信）。本文处理完全图识别问题，要求智能体确定其通信图是否为完全图。我们根据以下条件评估各种设置：(i) 由恶意调度程序保持的公平性——全局公平性或弱公平性，以及(ii) 智能体预先提供的知识——精确的人口规模n、n的公共上界P，或无先验信息。正面地，我们证明了在无先验信息的情况下，全局公平性下每智能体O(n²)个状态足以解决完全图识别问题。在知道n的情况下，智能体在弱公平性下仅使用O(n)个状态即可解决问题。负面地，我们证明了当仅知道人口规模n的公共上界P时，完全图识别在弱公平性下仍然不可解。
Keyword:
Population protocols
Graph class identification
期刊
IF:
1
论文数:
273
被引数:
1.0W
机构
引用论文
暂无论文信息