检索结果-内蒙古大学图书馆

DETECTING AND counting SMALL PATTERN GRAPHS

SIAM JOURNAL ON DISCRETE MATHEMATICS 2015年第3期29卷 1322-1339页

作者： Floderus, Peter Kowaluk, Miroslaw Lingas, Andrzej Lundell, Eva-Marta Lund Univ Ctr Math Sci S-22100 Lund Sweden Warsaw Univ Inst Informat Warsaw Poland Lund Univ Dept Comp Sci S-22100 Lund Sweden

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 slower combinatorial algorithm.

关键词： subgraph and induced subgraph isomorphism counting and detection of subgraphs polynomial testing exact algorithms randomized algorithms rectangular matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

counting AND DETECTING SMALL subgraphs VIA EQUATIONS

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2013年第2期27卷 892-909页

作者： Kowaluk, Miroslaw Lingas, Andrzej Lundell, Eva-Marta Warsaw Univ Inst Informat Warsaw Poland Lund Univ Dept Comp Sci S-22100 Lund Sweden

We present a general technique for detecting and counting small subgraphs. It consists of forming special linear combinations of the numbers of occurrences of different induced subgraphs of fixed size in a graph. These combinations can be efficiently computed by rectangular matrix multiplication. Our two main results utilizing the technique are as follows. Let H be a fixed graph with k vertices and an independent set of size s. 1. Detecting if an n-vertex graph contains a (not necessarily induced) subgraph isomorphic to H can be done in time O(n(omega(inverte right perpendicular(k-s)/2inverted letf perpendicular,1,1 right perpendicular(k- s)/2inverted letf perpendicular))), where omega(p, q, r) is the exponent of fast arithmetic matrix multiplication of an n(p) x n(q) matrix by an n(q) x n(r) matrix. 2. When s = 2, counting the number of (not necessarily induced) subgraphs isomorphic to H can be done in the same time, i.e., in time O(n(omega(inverted right perpendicular(k-2)/2inverted left perpendicular,1, inverted right perpendicular(k-2)/2inverted left perpendicular))). It follows in particular that we can count the number of subgraphs isomorphic to any H on four vertices that is not K-4 in time O(n(omega)), where omega = omega(1, 1, 1) is known to be smaller than 2.373. Similarly, we can count the number of subgraphs isomorphic to any H on five vertices that is not K-5 in time O(n(omega(2,1,1))), where omega(2, 1, 1) is known to be smaller than 3.257. Finally, we derive input-sensitive variants of our time upper bounds. They are partially expressed in terms of the number m of edges of the input graph and do not rely on fast matrix multiplication.

关键词： subgraph and induced subgraph isomorphism counting and detection of subgraphs linear equations exact algorithms rectangular matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：