Detecting and Counting Small Pattern Graphs
Detecting and Counting Small Pattern Graphs
复制标题
检测和计算小模式图
DOI：
--
复制
发表时间：
2013
影响因子：
0.8
通讯作者：
E. Lundell
中科院分区：
文献类型：
--
作者：
Peter Floderus;Miroslaw Kowaluk;A. Lingas;E. Lundell
研究了小模式图的导出子图同构问题和一般子图同构问题。我们提出了一个新的通用方法来检测同构于固定模式图的宿主图的诱导子图，通过减少到多项式测试的非同一性与零的有限特征的字段。它产生了新的上界的几个模式图的五个顶点，并提供了一个替代的组合方法的大多数模式图的四个和三个顶点。由于我们的方法避免了快速矩阵乘法的大开销，它可以是实际的兴趣，即使是较大的模式图。接下来，我们推导出新的时间上界计数的数量之间的同构的固定模式图与一个独立的一组大小$s$和一个子图的主机图。我们还考虑一个加权版本的计数问题，当一个计数的模式图和最轻的子图之间的同构的数量，提供一个稍微慢…
We study the induced subgraph isomorphism problem and the general subgraph isomorphism problem for small pattern graphs. We present a new general method for detecting induced subgraphs of a host graph isomorphic to a fixed pattern graph by reduction to polynomial testing for nonidentity with zero over a field of finite characteristic. It yields new upper time bounds for several pattern graphs on five vertices and provides an alternative combinatorial method for the majority of pattern graphs on four and three vertices. Since our method avoids the large overhead of fast matrix multiplication, it can be of practical interest even for larger pattern graphs. Next, we derive new upper time bounds on counting the number of isomorphisms between a fixed pattern graph with an independent set of size $s$ and a subgraph of the host graph. We also consider a weighted version of the counting problem, when one counts the number of isomorphisms between the pattern graph and lightest subgraphs, providing a slightly slowe...