We consider the fundamental problem of detecting/counting copies of a fixed pattern graph in a host graph. The recent progress on this problem has not included complete pattern graphs, i.e., cliques (and their complements, i.e., edge-free pattern graphs, in the induced setting). The fastest algorithms for the aforementioned patterns are based on a straightforward reduction to triangle detection/counting. We provide an alternative method of detection/counting copies of fixed size cliques based on a multi-dimensional matrix product. It is at least as time efficient as the triangle method in cases of $K_4$ and $K_5.$ The complexity of the multi-dimensional matrix product is of interest in its own rights. We provide also another alternative method for detection/counting $K_r$ copies, again time efficient for $r\in \{ 4,\ 5 \}$.


翻译:我们考虑了在主机图中探测/计算固定图案副本的根本问题,这个问题最近的进展没有包括完整的图案图案,即在诱导环境下的 cliques(及其补充,即无边图案图案),上述图案最快的算法是以直截了当地减少三角探测/计算为基础的。我们提供了一种基于多维矩阵产品的固定大小的样板的探测/计算替代方法。在4美元和5美元的情况下,它至少与三角法一样有效。多维矩阵产品的复杂性关系到其本身的权利。我们还提供了另一种探测/计算$_r$副本的替代方法,对于$_4,\ 5美元来说再次有效。

0
下载
关闭预览

相关内容

Python计算导论,560页pdf,Introduction to Computing Using Python
专知会员服务
72+阅读 · 2020年5月5日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
已删除
将门创投
4+阅读 · 2019年9月10日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
人脸检测库:libfacedetection
Python程序员
15+阅读 · 2019年3月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
车辆目标检测
数据挖掘入门与实战
30+阅读 · 2018年3月30日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
0+阅读 · 2021年11月23日
Clustered Object Detection in Aerial Images
Arxiv
5+阅读 · 2019年8月27日
Arxiv
3+阅读 · 2018年10月18日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
已删除
将门创投
4+阅读 · 2019年9月10日
计算机 | 入门级EI会议ICVRIS 2019诚邀稿件
Call4Papers
10+阅读 · 2019年6月24日
人脸检测库:libfacedetection
Python程序员
15+阅读 · 2019年3月22日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
车辆目标检测
数据挖掘入门与实战
30+阅读 · 2018年3月30日
Soft-NMS – Improving Object Detection With One Line of Code
统计学习与视觉计算组
6+阅读 · 2018年3月30日
【推荐】用Python/OpenCV实现增强现实
机器学习研究会
15+阅读 · 2017年11月16日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
【推荐】树莓派/OpenCV/dlib人脸定位/瞌睡检测
机器学习研究会
9+阅读 · 2017年10月24日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员