Finding a Maximum Clique.

reportActive / Technical Report | Accession Number: AD0738494 | Need Help?

Abstract:

An algorithm for finding a maximum clique in an arbitrary graph is described. The algorithm has a worst-case time bound of k1.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 34 as many vertices as the largest graph which the obvious algorithm examining all subsets of vertices can analyze. Author

Author(s):
Tarjan, Robert
Author Organization(s):
CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE
Descriptive Note:
Technical rept.,
Pagination:
0018

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:
Approved For Public Release

RECORD

Collection: TR
Identifying Numbers
Report Number(s):
CU-CSD-72-123
Contract/Grant Number(s):
N00014-67-A-0077-0021
 Subject Terms
Communities of Interest:
No COI(s) Identified
Descriptor(s):
(*GRAPHICS, ALGORITHMS), SET THEORY, POLYNOMIALS, THEOREMS
Field(s)/Group(s):
Theoretical Mathematics
Keyword(s):
CLIQUE GRAPHS, *GRAPHS, VENN DIAGRAMS
Report Date:
1972 Mar 01