A graph $G=(V,E)$ is a geometric intersection graph if every node $v \in V$ is identified with a geometric object of some particular type, and two nodes are adjacent if the corresponding objects intersect. Geometric intersection graph classes have been studied from both the theoretical and practical point of view. On the one hand, many hard problems can be efficiently solved or approximated when the input graph is restricted to a geometric intersection class of graphs. On the other hand, these graphs appear naturally in many applications such as sensor networks, scheduling problems, and others. Recently, in the context of distributed certification and distributed interactive proofs, the recognition of graph classes has started to be intensively studied. Different results related to the recognition of trees, bipartite graphs, bounded diameter graphs, triangle-free graphs, planar graphs, bounded genus graphs, $H$-minor free graphs, etc., have been obtained. The goal of the present work is to design efficient distributed protocols for the recognition of relevant geometric intersection graph classes, namely permutation graphs, trapezoid graphs, circle graphs, and polygon-circle graphs. More precisely, for the two first classes, we give proof labeling schemes recognizing them with logarithmic-sized certificates. For the other two classes, we give three-round distributed interactive protocols that use messages and certificates of size $\mathcal{O}(\log n)$. Finally, we provide logarithmic lower-bounds on the size of the certificates on the proof labeling schemes for the recognition of any of the aforementioned geometric intersection graph classes.


翻译:图形 $G= (V, E) 是一个几何交叉点图, 如果每个节点 $v\ in V$ 被识别为某特定类型的几何对象, 并且如果对应对象相交, 两个节点是相邻的。 已经从理论和实践角度研究了几何交叉图类 。 一方面, 当输入图限于几何交叉图表时, 许多难题可以有效解决或大致解决。 另一方面, 这些图表自然出现在许多应用程序中, 如传感器网络、 调度问题等 。 最近, 在分布式的认证和分布式交互式校对中, 图形类的识别已经开始深入研究。 不同的结果涉及到树的识别、 双叶图、 直径图、 无三角图、 捆绑式的基因图、 $H$$- minoror 等等。 目前工作的目标是设计有效的分布式协议, 用于识别相关的交互式图表类, 即 透度图表、 深色图、 更深色图的证书, 我们通过两个图表的图表, 向其它图表的排序提供。

0
下载
关闭预览

相关内容

IFIP TC13 Conference on Human-Computer Interaction是人机交互领域的研究者和实践者展示其工作的重要平台。多年来,这些会议吸引了来自几个国家和文化的研究人员。官网链接:http://interact2019.org/
【KDD2021】图神经网络,NUS- Xavier Bresson教授
专知会员服务
62+阅读 · 2021年8月20日
【图神经网络导论】Intro to Graph Neural Networks,176页ppt
专知会员服务
125+阅读 · 2021年6月4日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Improved Compression of the Okamura-Seymour Metric
Arxiv
0+阅读 · 2022年2月10日
Generalized Out-of-Distribution Detection: A Survey
Arxiv
15+阅读 · 2021年10月21日
Arxiv
8+阅读 · 2020年10月12日
Arxiv
19+阅读 · 2020年7月13日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
全球人工智能
19+阅读 · 2017年12月17日
【推荐】ResNet, AlexNet, VGG, Inception:各种卷积网络架构的理解
机器学习研究会
20+阅读 · 2017年12月17日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员