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
下载
关闭预览

相关内容

【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
37+阅读 · 2020年8月22日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
一份简单《图神经网络》教程,28页ppt
专知会员服务
120+阅读 · 2020年8月2日
Capsule Networks,胶囊网络,57页ppt,布法罗大学
专知会员服务
66+阅读 · 2020年2月29日
深度强化学习策略梯度教程,53页ppt
专知会员服务
177+阅读 · 2020年2月1日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Image Captioning 36页最新综述, 161篇参考文献
专知
90+阅读 · 2018年10月23日
计算机视觉领域顶会CVPR 2018 接受论文列表
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Capsule Networks教程
全球人工智能
10+阅读 · 2017年11月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Pointer Graph Networks
Arxiv
7+阅读 · 2020年6月11日
Arxiv
5+阅读 · 2019年6月5日
VIP会员
相关VIP内容
【如何做研究】How to research ,22页ppt
专知会员服务
108+阅读 · 2021年4月17日
图节点嵌入(Node Embeddings)概述,9页pdf
专知会员服务
37+阅读 · 2020年8月22日
神经常微分方程教程,50页ppt,A brief tutorial on Neural ODEs
专知会员服务
70+阅读 · 2020年8月2日
一份简单《图神经网络》教程,28页ppt
专知会员服务
120+阅读 · 2020年8月2日
Capsule Networks,胶囊网络,57页ppt,布法罗大学
专知会员服务
66+阅读 · 2020年2月29日
深度强化学习策略梯度教程,53页ppt
专知会员服务
177+阅读 · 2020年2月1日
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Hierarchically Structured Meta-learning
CreateAMind
23+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Image Captioning 36页最新综述, 161篇参考文献
专知
90+阅读 · 2018年10月23日
计算机视觉领域顶会CVPR 2018 接受论文列表
Hierarchical Imitation - Reinforcement Learning
CreateAMind
19+阅读 · 2018年5月25日
Capsule Networks教程
全球人工智能
10+阅读 · 2017年11月24日
【论文】变分推断(Variational inference)的总结
机器学习研究会
39+阅读 · 2017年11月16日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员