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):

Report Date:

1972-03-01

Pagination or Media Count:

18.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE