
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 worstcase 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