AllDifferent-based filtering for subgraph isomorphism
AllDifferent-based filtering for subgraph isomorphism
复制标题
DOI：
10.1016/j.artint.2010.05.002
复制
发表时间：
2010-08-01
影响因子：
14.4
通讯作者：
Solnon, Christine
中科院分区：
文献类型：
--
作者：
Solnon, Christine
子图同构问题涉及到判定目标图中是否存在模式图的副本。这个问题可以通过一个完整的树搜索与过滤技术相结合来解决，过滤技术旨在修剪不包含解决方案的分支。提出了一种基于局部所有不同约束的滤波算法。我们表明，这种过滤是强于其他现有的过滤-即，它修剪了更多的树枝-而且它也更有效-即，它允许人们更快地解决更多的实例。(C)2010 Elsevier BV保留所有权利。
The subgraph isomorphism problem involves deciding if there exists a copy of a pattern graph in a target graph. This problem may be solved by a complete tree search combined with filtering techniques that aim at pruning branches that do not contain solutions. We introduce a new filtering algorithm based on local all different constraints. We show that this filtering is stronger than other existing filterings - i.e., it prunes more branches - and that it is also more efficient - i.e., it allows one to solve more instances quicker. (C) 2010 Elsevier B.V. All rights reserved.