An algorithm for reporting maximal c-cliques

被引：11

作者：

Cazals, F ^{[1
]}

Karande, C

机构：

[1] INRIA, Sophia Antipolis, France

[2] Indian Inst Technol, Bombay, Maharashtra, India

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 349卷 / 03期

关键词：

maximal c-connected cliques; maximal-cliques; maximal common induced/edge subgraphs; shape matching;

D O I：

10.1016/j.tcs.2005.09.038

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 [计算机软件与理论];

摘要：

Given two graphs, a fundamental task faced by matching algorithms consists of computing either the (connected) maximal common induced subgraphs ((C)MCIS) or the (connected) maximal common edge subgraphs ((C)MCES). In particular, computing the CMCIS or CMCES reduces to reporting so-called c-connected cliques in product graphs, a problem for which an algorithm has been presented in I. Koch, Fundamental study: enumerating all connected maximal common subgraphs in two graphs, Theoret. Comput. Sci. 250 (1-2), (2001) 1-30. This algorithm suffers from two problems which are corrected in this note. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：484 / 490

页数：7

共 9 条

[1]

CAZALS F, 2005, 5615 INRIA

[2]

GARDINER EJ, 2000, J CHEM INF COMPUT SC, V40

[3]

GRINDLEY HM, 1993, J MOL BIOL, P229

[4]

Enumerating all connected maximal common subgraphs in two graphs [J].