# 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