Finding a Maximum Clique.
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 01, 1972
- Accession Number
- AD0738494
Entities
People
- Robert Tarjan
Organizations
- Department of Computer Science, Cornell University