Abstract
Making use of special tree search algorithms the present paper describes two new methods for determining all maximal complete subgraphs (cliques) of a finite nondirected graph. In both methods the blockwise generation of all cliques induces characteristic properties, which guarantee an efficient calculation of special clique subsets, especially the set of all cliques of maximal length. Moreover, by their structure both algorithms allow to calculate the complete clique set by parallel processing. The algorithms have been tested for many series of characteristic graphs and compared with the algorithm of Bron-Kerbosch (Algorithm 457 of CACM) the most efficient algorithm which is known to the authors.
Zusammenfassung
Die folgende Arbeit enthält zwei neue Algorithmen zur Bestimmung der Menge sämtlicher maximaler vollständiger Untergraphen (Cliquen) eines endlichen ungerichteten Graphen. Die Methoden verwenden spezielle Baumsuchalgorithmen. Die blockweise Erzeugung aller Cliquen führt zu charakteristischen Eigenschaften der Algorithmen, die eine effiziente Berechnung spezieller Untermengen von Cliquen, u.a. die Menge aller Cliquen von maximaler Länge, ermöglichen. Überdies erlaubt die Struktur beider Algorithmen die Berechnung der vollständigen Cliquenmenge auf parallel arbeitenden Rechnern. Die Algorithmen wurden an umfangreichen Serien charakteristischer Graphen getestet und mit dem wirksamsten der den Autoren bekannten Algorithmen, dem Algorithmus von Bron-Kerbosch (Algorithm 457 of CACM), verglichen.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bednarek, A. R., Taulbee, O. E.: On maximal chains. Roum. Math. Pures et Appl.11, 23–25 (1966).
Bron, C., Kerbosch, J.: Finding all cliques of an undirected graph. Collected algorithms from CACM (Algorithm 457). 1971.
Christofides, N.: An algorithm for the chromatic number of a graph. The Comp. J.14, 38 (1971).
Hakimi, S. L., Frank, H.: Maximum internally stable sets of a graph. J. of Math. Anal. and Appl.25, 296 (1969).
Harary, F., Ross, I. C.: A procedure for clique detection using the group matrix. Sociometry20, 205–215 (1957).
Johnson, L. F.: Determining cliques of a graph. Proc. of the fifth Conf. on Num. Math.1957, 429–437.
Leifman, L. J.: On construction of all maximal complete subgraphs (cliques) of a graph. Preprint, Dept. of Math., Univ. Haifa, Israel, 1976.
Meeusen, W., Cuyvers, L.: Clique detection in directed graphs: a new algorithm. J. of Comp. and Appl. Math.1, 185–193 (1975).
Maghout, K. H.: Sur la détermination des nombres de stabilité et du nombre chromatique d'un graph. C. r. Acad. Sci. (Paris)248, 3522–3523 (1959).
Moon, J. W., Moser, L.: On cliques in graphs. Israel J. Math.3, 23–28 (1965).
Peay, E. R., jr.: An iterative clique detection procedure. Michigan Math. Psychol. Program: MMPP 70-4 (1970).
Tinhofer, G.: Methoden der angewandten Graphentheorie (Kapitel 2, Algorithmus 8). Wien-New York: Springer 1976.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Gerhards, L., Lindenberg, W. Clique detection for nondirected graphs: Two new algorithms. Computing 21, 295–322 (1979). https://doi.org/10.1007/BF02248731
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02248731