The localization game is a pursuit-evasion game analogous to Cops and Robbers, where the robber is invisible and the cops send distance probes in an attempt to identify the location of the robber. We present a novel graph parameter called the capture time, which measures how long the localization game lasts assuming optimal play. We conjecture that the capture time is linear in the order of the graph, and show that the conjecture holds for graph families such as trees and interval graphs. We study bounds on the capture time for trees and its monotone property on induced subgraphs of trees and more general graphs. We give upper bounds for the capture time on the incidence graphs of projective planes. We finish with new bounds on the localization number and capture time using treewidth.


翻译:本地化游戏是一个类似于Cops和Robbers的追逐避险游戏, 抢匪是隐形的, 警方发送了远程探测器, 试图识别强盗的位置 。 我们展示了一个叫做抓捕时间的新型图形参数, 用来测量本地化游戏持续的时间, 以最佳游戏为最佳游戏。 我们推测抓捕时间按图表的顺序是线性的, 并显示图式家庭( 如树和间距图) 的猜想。 我们研究树木的捕捉时间和树的单体属性, 并研究树木的诱导子图和更普通的图形。 我们给投影式飞机的事件图表的捕捉时间以上方的上限 。 我们用本地化数字完成新的界限, 并用树丝来捕捉时间 。

0
下载
关闭预览

相关内容

图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
74+阅读 · 2020年8月2日
一份简单《图神经网络》教程,28页ppt
专知会员服务
127+阅读 · 2020年8月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
计算机视觉领域顶会CVPR 2018 接受论文列表
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
VIP会员
相关VIP内容
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
40+阅读 · 2020年8月22日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
74+阅读 · 2020年8月2日
一份简单《图神经网络》教程,28页ppt
专知会员服务
127+阅读 · 2020年8月2日
相关资讯
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
18+阅读 · 2018年12月24日
计算机视觉领域顶会CVPR 2018 接受论文列表
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员