Enumerating all connected maximal common subgraphs in two graphs
Theoretical Computer SciencePublished 1 January 2001
Ina Koch
Citations240
SJR quartileQ2
SJR score0.49
SNIP0.94
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A new method for finding all connected maximal common subgraphs in two graphs which is based on the transformation of the problem into the clique problem and the runtimes for all variants by means of random graphs are discussed.
Abstract
We represent a new method for finding all connected maximal common subgraphs in two graphs which is based on the transformation of the problem into the clique problem. We have developed new algorithms for enumerating all cliques that represent connected maximal common subgraphs. These algorithms are based on variants of the Bron–Kerbosch algorithm. In this paper we explain the transformation of the maximal common subgraph problem into the clique problem. We give a short summary of the variants of the Bron–Kerbosch algorithm in order to explain the modification of that algorithm such that the detected cliques represent connected maximal common subgraphs. After introducing and proving several variants of the modified algorithm we discuss the runtimes for all variants by means of random graphs. The results show the drastical reduction of the runtimes for the new algorithms.
Keywords
Computer Science
Communications of the ACMAlgorithm 457: finding all cliques of an undirected graph
2,451 Citations1973Coen Bron, Joep Kerbosch
Two backtracking algorithms are presented, using a branchand-bound technique [4] to cut off branches that cannot lead to a clique, and generates cliques in a rather unpredictable order in an attempt to minimize the number of branches to be traversed.
Birkhäuser Boston eBooksCongruent Graphs and the Connectivity of Graphs
806 Citations1992Hassler Whitney
SIAM Journal on ComputingAlgorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
530 Citations1972Fǎnicǎ Gavril
This paper presents ways for constructing efficient algorithms for finding a minimum coloring, a minimum covering by cliques, a maximum clique, and a maximum independent set given a chordal graph.
SIAM Journal on ComputingFinding a Maximum Independent Set
469 Citations1977Robert E. Tarjan, Anthony E. Trojanowski
An algorithm is presented which finds a maximum independent set in an n-vertex graph in 0($2^{n/3}$) time and can thus handle graphs roughly three times as large as could be analyzed using a naive algorithm.
Proteins Structure Function and BioinformaticsThreading a database of protein cores
446 Citations1995Thomas Madej, Jean‐François Gibrat +1 more
It would appear from the results that successful substructure recognition depends most critically on accurate definition of the “fold” of a database protein, which must correctly delineate substructures that are, and are not, likely to be conserved during protein evolution.
SIAM Journal on ComputingFinding a Maximum Clique in an Arbitrary Graph
288 Citations1986Egon Balas, Chang Sung Yu
A new type of branch and bound procedure for finding a maximum clique in an arbitrary graph G, which discusses computational experience on randomly generated graphs with up to 400 vertices and 30,000 edges.
Journal of Molecular BiologyIdentification of Tertiary Structure Resemblance in Proteins Using a Maximal Common Subgraph Isomorphism Algorithm
269 Citations1993Helen M. Grindley, Peter J. Artymiuk +2 more
A program called PROTEP is described that permits the rapid comparison of pairs of three-dimensional protein structures to identify the patterns of secondary structure elements that they have in common, using a maximal common subgraph isomorphism algorithm that is based on a clique detection procedure.
CALCOLOA note on the derivation of maximal common subgraphs of two directed or undirected graphs
226 Citations1973Giorgio Levi
A technique is described by which this problem of finding maximal common subgraphs of two given graphs can be stated as a problem of deriving maximal compatibility classes and the same technique is shown to apply to the classical subgraph isomorphism problem.
SIAM Journal on ComputingThe Enumeration of Maximal Cliques of Large Graphs
172 Citations1973E. A. Akkoyunlu
An algorithm for enumerating maximal cliques (complete subgraphs) is proposed, which aims to deal with the difficulties caused by the size of the problem.
Journal of Chemical Information and Computer SciencesAlgorithms for the identification of three-dimensional maximal common substructures
160 Citations1987Andrew Brint, Peter Willett
Two algorithms are described for the identification of the maximal substructures common to two (or more) three-dimensional chemical structures, where a substructure consists of a set of atoms and the associated interatomic distances.
Journal of Computational BiologyAn Algorithm for Finding Maximal Common Subtopologies in a Set of Protein Structures
126 Citations1996Ina Koch, Thomas Lengauer +1 more
A new suitable representation of the secondary structure topology of a protein by an undirected labeled graph is described and a new fast algorithm is developed that finds all common subtopologies in a set of protein structures.
International Journal of Parallel ProgrammingCliques of a graph-variations on the Bron-Kerbosch algorithm
102 Citations1976H. C. Johnston
A family of algorithms that are variations on the Bron-Kerbosch algorithm for finding all the cliques of a simple undirected graph are developed in a stepwise manner from a recursive algorithm for generating all combinations of zero or more objects chosen fromN objects.
Protein Engineering Design and SelectionComparison of spatial arrangements of secondary structural elements in proteins
98 Citations1995Kenji Mizuguchi, Nobuhiro Gō
A new method of protein structure comparison based on spatial arrangements of secondary structural elements (SSEs) that has a flexible target function that can be adjusted depending upon particular levels or definitions of structural similarity, and it is fast enough to allow structural comparisons for many pairs of proteins.
Mathematical Methods of Operations ResearchA branch and bound algorithm for the maximum clique problem
58 Citations1990Luitpold Babel, G. Tinhofer
A branch and bound algorithm for the maximum clique problem in arbitrary graphs is presented using a modification of a known graph coloring method called DSATUR to simultaneously derive lower and upper bounds for the clique number.
ComputingClique detection for nondirected graphs: Two new algorithms
49 Citations1979Leonhard Gerhards, Wolfgang Lindenberg
Two new methods for determining all maximal complete subgraphs (cliques) of a finite nondirected graph are described, in both methods the blockwise generation of all cliques induces characteristic properties, which guarantee an efficient calculation of special clique subsets.
Mathematical ProgrammingA polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
33 Citations1981Wen−Lian Hsu, Yoshiro Ikura +1 more
An O(n2K+1) algorithm for the maximum weighted vertex packing problem for graphs inG ≥ 1 and an algorithm for piecing together maximum weighted packings on blocks to find maximum weightedPackings on graphs that contain more than one block are presented.
Naval Research Logistics QuarterlyA node covering algorithm
21 Citations1977Egon Balas, Haakon M. Samuelsson
The algorithm is based on the concept of a dual node-clique set, which allows us to identify partial covers associated with integer dual feasible solutions to the linear programming equivalent of the node covering problem.
PubMedDetection of distant structural similarities in a set of proteins using a fast graph-based method.
15 Citations1997Ina Koch, Thomas Lengauer
It is suggested that for detecting the similarities between two protein structures it is sufficient to find similarities in the protein core which consists of tightly packed secondary structure elements and the common substructure in all proteins can be calculated by intersecting them.