Accession Number : AD0738494

Title :   Finding a Maximum Clique.

Descriptive Note : Technical rept.,

Corporate Author : CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s) : Tarjan,Robert

Report Date : MAR 1972

Pagination or Media Count : 18

Abstract : An algorithm for finding a maximum clique in an arbitrary graph is described. The algorithm has a worst-case time bound of k(1.286) sup N for some constant k, where n is the number of vertices in the graph. Within a fixed time, the algorithm can analyze a graph with 2 3/4 as many vertices as the largest graph which the obvious algorithm (examining all subsets of vertices) can analyze. (Author)

Descriptors :   (*GRAPHICS, ALGORITHMS), SET THEORY, POLYNOMIALS, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE