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
Descriptors:
Subject Categories:
- Theoretical Mathematics