A note on the problem of reporting maximal cliques
A note on the problem of reporting maximal cliques
复制标题
DOI：
10.1016/j.tcs.2008.05.010
复制
发表时间：
2008-11-06
影响因子：
1.1
通讯作者：
Karande, C.
中科院分区：
文献类型：
--
作者：
Calzals, F.;Karande, C.
图的最大团是一个在许多领域都存在的基本问题。本文弥补了Bron-Kerbosh [C. Bron，J. Kerbosch，Algorithm 457：Finding all clues of an undirected graph，Communication of ACM 16（9）（1973）575-577]，以及最近发表在TCS上的两篇论文，即Tomita等人的论文[Tomita，A.田中，H. Takahashi，The worst-case time complex for generating all maximum clues and computational experiments，Theoretical Computer Science 363（1）（2006）28-42]，以及Koch的[I. Koch，Fundamental study：Enumerating all connected maximum common subgraphs in two graphs，Theoretical Computer Science 250（1-2）（2001）1-30].特别是，我们表明，富田等人的战略。是一个简单的修改的布朗-Kerbosch算法，根据（未开发）观察科赫的论文。(C)2008 Elsevier B. V.保留所有权利。
Reporting the maximal cliques of a graph is a fundamental problem arising in many areas. This note bridges the gap between three papers addressing this problem: the original paper of Bron-Kerbosh [C. Bron, J. Kerbosch, Algorithm 457: Finding all cliques of an undirected graph, Communication of ACM 16 (9) (1973) 575-577], and two papers recently published in TCS, namely that of Tomita et al. [Tomita, A. Tanaka, H. Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science 363 (1) (2006) 28-42], and that of Koch [I. Koch, Fundamental study: Enumerating all connected maximal common subgraphs in two graphs, Theoretical Computer Science 250 (1-2) (2001) 1-30]. In particular, we show that the strategy of Tomita et al. is a simple modification of the Bron-Kerbosch algorithm, based on an (un-exploited) observation raised in Koch's paper. (C) 2008 Elsevier B.V. All rights reserved.