% Pardalos and Xue survey clique paper
% To appear in the Journal of Global Optimization
\documentstyle[11pt]{article}
\clubpenalty = 100
\widowpenalty = 100
\interlinepenalty = 100
\raggedbottom

\newcommand{\drawline}{\rule{4.5in}{.4mm}}
\newtheorem{lem}{Lemma}[section]
\newtheorem{thm}{Theorem}[section]

\begin{document}
\title{The Maximum Clique Problem}
\author{Panos M. Pardalos \\
Department of Industrial and Systems Engineering \\
303 Weil Hall \\
University of Florida \\
Gainesville, FL 32611 \\
 \and Jue Xue \\Graduate School of Management\\
Clark University \\
950 Main Street\\
 Worcester, MA 01610}
\date{August 20, 1992}
\maketitle
\begin{abstract}
In this paper we present a survey of results concerning algorithms,
complexity, and applications of the maximum clique problem. We
discuss enumerative and exact algorithms, heuristics, and a variety
of other proposed methods. An up to date bibliography on the maximum
clique and related problems is also provided.

{\bf Key words:} maximum clique problem, graph coloring, heuristics,
algorithms, $NP$-hard, bibliography, survey.
\end{abstract}


\section{Introduction}

Throughout this paper, $G = (V,E)$ is an arbitrary undirected and
weighted graph unless otherwise specified. $V = \{1,2,\ldots,n \}$
is the vertex set of $G$, and $E \subseteq V \times V$ is the edge
set of $G$. For each vertex $i \in V$, a positive weight $w_i$ is
associated with $i$. $A_G=(a_{ij})_{n \times n}$ is the adjacency
matrix of $G$, where $a_{ij} = 1$ if $(i,j) \in E$ is an edge of
$G$, and $a_{ij}=0$ if $(i,j) \notin E$.

The {\em complement graph of} $G = (V,E)$ is the graph
$\overline{G} = (V,\overline{E})$, where
$\overline{E} = \{(i,j) \; | \; i,j \in V, \; i \neq j \;
 \mbox{and } (i,j) \notin E \}$.
For a subset $S \subseteq V$, we define the weight of $S$ to be
$W(S) = \sum_{i \in S} w_i$. We call
$G(S) = (S, E \cap S \times S)$ {\em the subgraph induced by $S$}.

A graph $G = (V,E)$ is {\em complete} if all its vertices are
pairwise adjacent, i.e. $\forall i, \, j \in V, \; (i,j) \in E$. A
{\em clique } $C$ is a subset of $V$ such that $G(C)$ is complete.
The maximum clique problem asks for a clique of maximum cardinality.
The maximum weight clique problem asks for a clique of maximum
weight.

An {\em independent set} ({\em stable set, vertex packing}) is a
subset of $V$, whose elements are pairwise nonadjacent. The maximum
independent set problem asks for an independent set of maximum
cardinality. The size of a maximum independent set is the
{\em stability number} of G (denoted by $\alpha(G)$). The maximum
weight independent set problem asks for an independent set of
maximum weight.

We should distinguish a {\em maximum} clique (independent set) from
a {\em maximal} clique (independent set). A maximal clique
(independent set) is a clique (independent set) that is not a subset
of any other clique (independent set). A maximum clique (independent
set) is a maximal clique (independent set) that has the maximum
cardinality or weight.

A {\em vertex cover} is a subset of $V$, such that every edge
$(i,j) \in E$ has at least one endpoint $i$ or $j$ in the subset.
The minimum vertex cover problem asks for a vertex cover of minimum
cardinality. The minimum weighted vertex cover problem asks for a
vertex cover of minimum weight. 


It is easy to see that $S$ is a clique of $G$ if and only if $S$ is
an independent set of $\overline{G}$, and if and only if
$V \setminus S$ is a vertex cover of $\overline{G}$. Any result
obtained for one of the above problems has its equivalent forms for
the other problems. Furthermore, these problems are $NP$-complete on
arbitrary graphs (see Gary and Johnson \cite{GaJo79}).

The maximum clique problem has many equivalent formulations as an
integer programming problem, or as a continuous nonconvex
optimization problem. The simplest one is the following
{\em edge formulation}:

\begin{equation}
\mbox{max} \; \sum_{i=1}^{n} w_{i} x_{i},
	\label{mcef}
\end{equation}
\[ \mbox{s.t. } x_i + x_j \leq 1, \;
	\forall \; (i,j) \in \overline{E}, \]
\[ x_{i} \in \{0,1\}, \; i = 1, \ldots, n. \]

A polyhedral result concerning formulation (\ref{mcef}) is due to
Nemhauser and Trotter (\cite{NeTr74}, \cite{NeTr75}). In 1975 they
found that if a variable $x_i$ had integer value $1$ in an optimal
solution to the linear relaxation of (\ref{mcef}), then $x_i = 1$
in at least one optimal solution to (\ref{mcef}).

\begin{thm}
{\em (see \cite{NeTr75}, also \cite{PiQu77})}
Let $x$ be an optimum $(0, \frac{1}{2}, 1)$-valued solution to the
linear relaxation of $(\ref{mcef})$, and let
$P = \{j \; | \; x_{j} = 1 \}$. There exists an optimum solution
$x^{*}$ to $(\ref{mcef})$ such that $x^{*}_j = 1, \; \forall j \in  
P$.
	\label{thm01}
\end{thm}

This theorem suggests an implicit enumerative algorithm for
(\ref{mcef}) via solving its linear relaxation problem. However, in
most cases, few variables have integer values in an optimal solution
to the linear relaxation of (\ref{mcef}), and the gap between the
optimal values of (\ref{mcef}) and its linear relaxation problem is
too large. These seriously restrict the use of this approach.

Let $\cal S$ denote the set of all maximal independent sets of $G$.
An alternative formulation is the following {\em independent set}
formulation.

\begin{equation}
\mbox{max } \sum_{i=1}^{n} w_{i} x_{i},
	\label{mcsf}
\end{equation}
\[ \mbox{s.t. } \sum_{i \in S} x_{i} \leq 1, \;
	\forall S \in \cal S, \]
\[ x_{i} \in \{0,1\}, \; i = 1, \ldots, n. \]
The advantage of formulation (\ref{mcsf}) over (\ref{mcef}) is a
smaller gap between the optimal values of (\ref{mcsf}) and its
linear relaxation. However, since the number of constraints in
(\ref{mcsf}) is exponential, solving the linear relaxation of
(\ref{mcsf}) is not an easy problem. In fact, Gr\"{o}teschel et al
(\cite{GrLoSc86} and \cite{GrLoSc88}) have shown that the linear
relaxation problem of
(\ref{mcsf}) is $NP$-hard on general graphs. They have also shown
that the same problem is polynomially solvable on {\em perfect}
graphs. Furthermore, they have shown that a graph is perfect if and
only if the optimal solution to the linear relaxation of
(\ref{mcsf}) always assume integer values. The following results can
be found from \cite{GrLoSc81}, \cite{GrLoSc86}, \cite{GrLoSc88}, and
\cite{GrLoSc89}.

\begin{thm}
Let G be an arbitrary graph. The linear relaxation problem of
$(\ref{mcsf})$ is NP-complete.
	\label{thm02}
\end{thm}

\begin{thm}
G is a perfect graph if and only if the linear relaxation of
$(\ref{mcsf})$ has integer solutions for any $w \in R^{n}$.
	\label{thm03}
\end{thm}

\begin{thm}
The maximum weight clique problem for perfect graphs can be solved
in polynomial time.
	\label{thm04}
\end{thm}

Besides the above formulations for the maximum clique problem, we
can also find in the literature many other formulations. For
example, consider the following indefinite \cite{PaRo87} quadratic
problem

\begin{equation}
\mbox{global } \max f(x) = \frac{1}{2} x^{T} A_{G} x, 
	\label{iqpb}
\end{equation}
\[ \mbox{s.t. } \sum_{i=1}^{n} x_{i} = 1, \; x_{i} \geq 0, \;
	i = 1,\ldots,n. \]
In theorem 1 of Motzkin and Straus \cite{MoSt65}, the following
result was proved (see also \cite{AhErLi88}). 



\begin{thm}
Let $x^{*} \; and \; \alpha = f(x^{*})$ be the optimal solution and
the corresponding objective value of problem $(\ref{iqpb})$.
Then $G$ has a maximum clique $C$ of size $k = 1/(1 - 2 \alpha)$.
The global maximum of $(\ref{iqpb})$ can be attained by setting
$x^{*}_{i} = \frac{1}{k}$ if $v_{i} \in C$, and $x^{*}_{i} = 0$
otherwise.
	\label{thm1}
\end{thm}

Although this characterization does not provide an efficient
approach to solve the maximum clique problem, it can be used to
prove certain bounds on the size of the maximum clique. The
following theorem is a consequence of a more general result from
Hager et al \cite{HaPaRoSa87}.

\begin{thm}
If $A_{G}$ has $r$ negative eigenvalues, then at least $n-r$
constraints are active at any global maximum $x^{*}$ of $f(x)$.
	\label{thm11} 


\end{thm}

Here, by active constraints of (\ref{iqpb}) at a global maximum
$x^{*}$, we mean those constraints $x_i \geq 0$ satisfying
$x^{*}_i = 0, i = 1, \ldots, n$. Note that the constraint
$\sum_{i=1}^{n} x_{i} = 1$ is always active by definition. Combining
theorems \ref{thm1} and \ref{thm11}, we can obtain an upper bound on
the size of the maximum clique of $G$ (see also Pardalos and
Phillips \cite{PaPh90}): If $A_{G}$ has $r$ negative eigenvalues,
the size $|C|$ of the maximum clique $C$ is bounded by
$|C| \leq r + 1$. 


In 1990, Shor (\cite{Sho90}) considered an interesting
formulation of the maximum weight independent set problem. Note that
the maximum weight independent set problem can be formulated as 


\begin{equation}
\mbox{global } \min f(x) = \sum_{i=1}^{n} w_i x_i,
	\label{Clique:12}
\end{equation}
\[ \mbox{s.t.} \; {x}_{i} + {x}_{j} \leq 1, \; \forall \;
 (i,j) \in E, \; x \in { \{ 0, 1 \} }^{n}. \]

The above formulation is equivalent to the following quadratically
constrained global optimization problem

\begin{equation}
\mbox{global } \min f(x) = \sum_{i=1}^{n} w_i x_i,
	\label{Clique:13}
\end{equation}
\[ \mbox{s.t.} \; {x}_{i}{x}_{j} = 0, \; \forall \; (i,j) \in E, \]
\[ {x_i}^2 - x_i = 0, \; i = 1, 2, ..., n. \]

Applying dual quadratic estimates, Shor reported very good
computational results using (\ref{Clique:13}). It seems that for the
maximum clique problem, a {\em good} formulation of the problem is
of crucial importance in solving the problem. 


The general {\em quadratic optimization} problem is of the form
\begin{equation}
\min f(x) = c^{T} x + \frac{1}{2} x^{T} Qx,
	\label{qo}
\end{equation}
\[ \mbox{s.t.} \; A x = b, \; x \in D, \]
where $c \in R^n$, $Q \in R^{n \times n}$, $A \in R^{m \times n}$,
and $D \subseteq R^{n}$. 


Next, we formulate the maximum clique, the maximum independent set
and the maximum weight independent set problems as quadratic
zero-one problems. We use $I$ to denote the $n\times n$ identity
matrix. To facilitate our discussion, define a transformation $T$
from $\{0,1\}^n$ to $2^V$,
\[ T(x) = \{ i \; | \; x_i = 1, \; i \in V \}, \;
 \forall \; x \in \{0,1\}^n. \]
Denote the inverse of $T$ by $T^{-1}$. If $x = T^{-1}(S)$ for some
$S \in 2^V$ then $x_i = 1 \mbox{ if } i \in S$ and
$x_i = 0 \mbox{ if } i \not \in S, \; i = 1, \ldots, n$.

We can rewrite the maximum problem (\ref{mcef}) as a minimization
problem (when $x_i = 1$)
\begin{equation}
\mbox{global } \min f(x) = - \sum_{i=1}^{n} x_i,
	\label{Clique:1}
\end{equation} 


\[ \mbox{s.t.} \; {x}_{i} + {x}_{j} \leq 1, \;
 \forall \; (i,j) \in \overline{E}, \; x \in { \{ 0, 1 \} }^{n}. \]
If ${x}^{*}$ solves (\ref{Clique:1}), then the set $C = T(x^{*})$ is
a maximum clique of $G$ with $|C| = -z = - f({x}^{*})$.

Another way of stating the constraints for (\ref{Clique:1}) is to
make use of the fact that the quadratic expressions
${x}_{i} {x}_{j} = 0$ for all $(i,j) \in \overline{E}$ since for
${x}_{i} , {x}_{j} \in { \{ 0,1 \} } \; {x}_{i} + {x}_{j} \leq 1$ if
and only if ${x}_{i} {x}_{j} =0 $. The constraints in
(\ref{Clique:1}) can be removed by adding two times the quadratic
terms to the objective function, which is now
\[ f(x) = - \sum_{i=1}^{n}{ {x}_{i} } +
 2 \sum_{ (i,j) \in \overline{E}, \; i > j }
 {x}_{i} {x}_{j} = {x}^{T} ( A_{\overline{G}} - I ) x. \]
The quadratic terms represent penalties for violations of
${x}_{i} {x}_{j} = 0$. This leads to the following theorem.

\begin{thm}
The maximum clique problem is equivalent to the following global
quadratic zero-one problem
\begin{equation}
\mbox{global } \min f(x) = {x}^{T} Ax,
	\label{Clique:4}
\end{equation}
\[ \mbox{s.t.} \; x \in { \{ 0,1 \} }^{n}, \;
 \mbox{where} \; A = {A}_{ \overline{G} } - I. \]
If ${x}^{*}$ solves $(\ref{Clique:4})$, then the set $C$ defined
by $C = T(x^{*})$ is a maximum clique of $G$ with
$|C| = -z = -f({x}^{*})$.
	\label{thm21}
\end{thm}

The off-diagonal elements of the matrix $A$ are the same as the
adjacency matrix of $\overline{G}$. Hence, formulations
(\ref{Clique:1}) and (\ref{Clique:4}) are advantageous for dense
graphs because a sparse data structure can be used (for details, see
\cite{PaRo90.2}). Following the equivalence of the maximum clique
problem with the maximum independent set problem, we have

\begin{thm}
The maximum independent set problem is equivalent to the following
global quadratic zero-one problem
\begin{equation}
\mbox{global } \min {f(x) = {x}^{T} Ax}
	\label{Clique:5}
\end{equation}
\[ \mbox{s.t.} \; x \in { \{ 0,1 \} }^{n}, \;
 \mbox{where} \; A = {A}_{G} - I. \]
If ${x}^{*}$ solves $(\ref{Clique:5})$, then the set $S$ defined
by $S = T(x^{*})$ is a maximum independent set of $G$ with
$|S| = -z = - f({x}^{*})$. 


	\label{thm22}
\end{thm}

Next, we discuss the maximum weight independent set problem. The
above theorems for the maximum clique problem and the maximum
independent set problem can be regarded as a special case by taking
$w_i = 1, i = 1, 2, \ldots, n$.

\begin{thm}
The maximum weight independent set problem is equivalent to the
following global quadratic zero-one problem
\begin{equation}
\mbox{global } \min f(x) = {x}^{T} Ax,
	\label{Clique:6}
\end{equation}
\[ \mbox{s.t.} \; x \in { \{ 0,1 \} }^{n}, \]
where $ {a}_{ii} = - {w}_{i}, \; i = 1, ..., n, \;
{a}_{ij} = \frac{1}{2} ({w}_{i} + {w}_{j}), \;
\forall \; (i,j) \in E$, and ${a}_{ij} = 0, \;
\forall \; (i,j) \in \overline{E}$.

Let ${x}^{*}$ solve $(\ref{Clique:6})$, then the set $S$ defined
by $S = T(x^{*})$ is a maximum independent set of $G$ with weight
$W(S) = -z = - f({x}^{*})$.
	\label{thm23}
\end{thm}

As with many problems of combinatorial optimization, using the 
appropriate formulation of the maximum clique problem is of crucial
importance in solving the problem. In addition, using different
formulations, we gain more insight into the problem's complexity
and we can prove intertesting results.

\section{Complexity}

The maximum clique, maximum independent set and minimum vertex cover
problems are computationally equivalent on arbitrary graphs. They
are also known to be $NP$-complete. Furthermore, for the maximum
clique problem, the complexity of approximating remained an open
question until recently. In \cite{PaYa88}, Papadimitriou and
Yannakakis introduced the complexity class $MAX \, SNP$ and showed
that many natural problems are complete in this class, relative to a
reducibility that preserves the quality of approximation. For
example, the vertex cover problem (for constant degree graphs), min
cut problem, dominating set problem, and the MAX 3-SAT problem are
such complete problems \cite{Yan92}.

If the solution to any of these complete problems can be
approximated to arbitrary small constant factors, then the optimum
solution to any problem in the class can be approximated to
arbitrarily small constant factors. The question of whether such
approximation schemes can be found for the complete problems in this
class was left unresolved. In \cite{BeSc89}, Berman and Schnitger
have shown that if one of the $MAX \, SNP$ problems does not have
polynomial time approximation schemes, then there is an $\epsilon >
0$ such that the maximum clique problem cannot be approximated in
polynomial time with performance ratio

\[ \mbox{} \frac{size \; of \; maximum \; clique}{size \; of \;
 approximate \; clique} = O(n^{\epsilon}), \]
where $n$ is the number of vertices in the graph (see also Feige et
al \cite{FeGoLoSaSz91}, where a connection between approximation
complexity and interactive proof systems is discussed). 


A breakthrough in approximation complexity is the recent result by
Arora et al \cite{ArLuMo92}, \cite{ArSa92}. It is shown that the
maximum number of satisfiable clauses in a 3-SAT formula (MAX 3-SAT)
cannot be approximated to arbitrary small constants (unless $P =
NP$), thus resolving the open question in \cite{PaYa88}. This
immediately shows the hardness of finding good approximate solutions
to all the above listed problems. In particular, it is shown that no
polynomial time algorithm can approximate the maximum clique size
within a factor of $n^{\epsilon}$ ($\epsilon > 0$), unless $P = NP$
(by using the results of Feige et al \cite{FeGoLoSaSz91}).

Although these complexity results characterize worst case instances,
they nevertheless indicate that the maximum clique problem is indeed
a very difficult problem to solve.

Some other results in the literature concerning the approximation of
the maximum clique/independent set problem on arbitrary or special
graphs can be found in \cite{BoHa90}, \cite{ChNiSa82},
\cite{ChFr86}, \cite{CrFiSi91}, \cite{Mur92}, \cite{Rag88}.

If we restrict ourselves to graphs with special structure, then in
many cases the maximum clique/independent set problem can be solved
in polynomial time. For example, Balas et al (\cite{BaChNe87})
introduced several classes of graphs and showed that the maximum
weight clique problem can be solved in polynomial time on them. In
Balas and Yu (\cite{BaYu89}), they discussed classes of graphs that
have polynomially many maximal cliques. On those graphs, the maximum
weight clique problem can also be solved in polynomial time.

A well known class of graphs where the maximum clique problem is
polynomially solvable, is the class of perfect graphs
(\cite{BeCh84}). A graph $G$ is perfect if every induced subgraph of
$G$ has the property that the size of its maximum clique equals 

the minimum number of independent sets needed to cover all the
vertices (commonly called a {\em coloring} in the literature). Since
the complement graph of a perfect graph is also perfect, theorem
\ref{thm04} of the last section states that the maximum clique
problem can be solved in polynomial time on perfect graphs and their
complements. The class of perfect graphs contains many well know
graphs in the literature (see \cite{Gol80}). For example, bipartite
graphs, interval graphs, and triangulated graphs (\cite{Gav72},
\cite{Fra76}, \cite{Ros70}, \cite{RoTaLe76}, \cite{TaYa84}).
Examples of more recently found perfect graphs are {\em Meyniel
graphs} (\cite{Mey76}, \cite{BuFo84}), {\em quasi parity graphs}
(\cite{Mey85}), {\em weakly triangulated graphs} (\cite{Hay85},
\cite{HaHoMa90}), {\em perfectly orderable graphs} (\cite{Chv85})
and {\em unimodular graphs} (\cite{Hel57}).

A class of graphs that is closely related to the perfect graphs is
the {\em t-perfect} graphs. This class of graphs was defined in
\cite{Chv75}. Polynomial algorithms for the maximum weight
independent set problem on {\em t-perfect} graphs exist
(\cite{GrLoSc88}). The class of {\em t-perfect} graphs contains
{\em bipartite graphs, series-parallel graphs} (\cite{Dir52},
\cite{Chv75}, \cite{BoUh79}), and {\em strongly t-perfect graphs}
(\cite{GeSc86}). For a polynomial time algorithm for solving the
maximum weight independent set problem on a bipartite graph
$G( V_1 , V_2 )$ see the book by Lawler \cite{Law76}. 


Other special classes of graphs where the maximum clique/independent
set problem have been studied in the literature can be found in
\cite{Bal86}, \cite{Bur89}, \cite{ChNiSa82}, \cite{ChNiSa83},
\cite{ChNa91}, \cite{ChFr86}, \cite{Dir61}, \cite{Gav73},
\cite{Gav74}, \cite{GoHa88}, \cite{GrPu85}, \cite{GuLeLe82},
\cite{HoLe88}, \cite{Hsu85}, \cite{Hsu88}, \cite{HsIkNe81},
\cite{KaMaNaFu92} \cite{Kle88}, \cite{MaNa88}, \cite{MaNaKaFu90},
\cite{Min80}, \cite{NaNaSc87}, \cite{Ola89}, \cite{PaYa81},
\cite{Pul79}, \cite{RoUr81}, \cite{Sag88}, \cite{TaChLeHu90}. 


We should note here that the weighted or unweighted version of the
maximum clique problem, the maximum independent set problem, and
the minimum vertex cover problem may not be equivalent on graphs with
special structures.

\section{Enumerative Algorithms}

The first algorithm for enumerating all cliques of an arbitrary
graph in the literature is probably due to Harary and Ross
\cite{HaRo57}. In 1957, they proposed an inductive method that first
identified all the cliques of a given graph with no more than three
cliques. Then the problem on general graph is reduced to this
special case. Their work was stimulated by the matrix manipulation
problem of sociometric data to find a complete identification of
cliques.

Early works following that of Harary and Ross \cite{HaRo57} can be
found in Maghout \cite{Mag59}, Paull and Unger \cite{PaUn59}, Bonner
\cite{Bon64}, Marcus \cite{Mar64}, and Bednarek and Taulbee
\cite{BeTa66}, \cite{Dor69}. What Paull and Unger (\cite{PaUn59}),
and Marcus (\cite{Mar64}) proposed were algorithms to minimize the
number of rows in a flow table for a sequential switching function.
The problem addressed in Bonner (\cite{Bon64}) was the clustering
problem in information systems. Bednarek and Taulbee \cite{BeTa66}
proposed algorithms for generating all maximal chains of a set with
a binary relation defined on it. Although these problems come from
different fields and appear dealing with different problems, they
are solving the same problem of enumerating all cliques of a graph.
With the technology at that time, these early algorithms could only
be tested on special graphs.

In 1970, Auguston and Minker \cite{AuMi70} investigated several
graph theoretic clustering techniques used in information systems.
In their work, the algorithm of Bierstone (see \cite{AuMi70},
\cite{MuCo72}) and the algorithm of Bonner \cite{Bon64} were tested.
The method used in both algorithms was called the {\em vertex
sequence method} or {\em point removal method}. This method produces
cliques of $G$ from the cliques of $G-v$, $v \in G$. From their
computational results, they found the algorithm of Bierstone was
more efficient. The original work of Bierstone was not published.
The version of Bierstone's algorithm contained in Auguston and
Minker \cite{AuMi70} had two errors that were corrected by Mulligan
and Corneil \cite{MuCo72} in 1972. 


Then in 1973, two new algorithms using the {\em backtracking method}
were proposed by Akkoyunlu \cite{Akk73}, and by Bron and Kerbosch
\cite{BrKe73}. The advantage of the backtracking method is the
elimination of the redundancy in generating the same clique. What
was more important for these two algorithms was their polynomial
storage requirements. For example, the Bron and Kerbosch algorithm
requires at most $\frac{1}{2}n(n+3)$ storage space. Bron and
Kerbosch tested their algorithm on graphs of 10 to 50 vertices and
densities ranging from 10\% to 95\%. Here the density was defined as
the probability of a pair of vertices being connected. They found
their algorithm was much more efficient than
Bierstone's algorithm. One very interesting phenomenon from their
test was the ratio of CPU time over the number of cliques of the
graph, as they put it, ``hardly dependent on the size of the
graph''. Bron and Kerbosch's algorithm is {\em Algorithm 457}
in the ACM collection.

More enumerative algorithms were proposed in the 70's following that
of Bron and Kerbosch. For example, the works by Osteen and Tou
\cite{OsTo73}, Osteen \cite{Ost74}, Meeusen and Cuyvers
\cite{MeCu75}, Johnson \cite{Joh75}, Johnston \cite{Joh76}, Leifman
\cite{Lei76}, Tsukiyama et al \cite{TsIdAvSh77}, Gerhards and
Lindenberg \cite{GeLi79}.

The algorithm of Osteen and Tou \cite{OsTo73} was an improved
version of the point removal method. Osteen's \cite{Ost74} algorithm
was designed for a special class of graphs. The algorithm of Meeusen
and Cuyvers \cite{MeCu75} started with decomposing a graph into
subgraphs satisfying {\em the chain of subsets in G} requirement.
Such a decomposition had the property that every clique is contained
completely in at least one subgraph. Based on this property, they
proposed an algorithm to find all cliques of a graph. The work of
Johnston \cite{Joh76} contains a family of algorithms that are
variations of Bron and Kerbosch's algorithm. By comparing several
algorithms computationally, Johnston \cite{Joh76} concluded that the
Bron and Kerbosch algorithm was one of the most efficient algorithms.

Tsukiyama et al \cite{TsIdAvSh77} proposed an enumerative algorithm
that combined the approaches used by Auguston and Minker
\cite{AuMi70}, Akkoyunlu \cite{Akk73}, and Bron and Kerbosch
\cite{BrKe73}. The result was an algorithm with time complexity of
$O(nm \mu)$ and storage requirement of $O(n+m)$, where $n, m, \mu$
are the number of vertices, edges and maximal cliques of a graph.
This bound is stronger than the earlier bound of $O(\mu^{2})$
due to Auguston and Minker \cite{AuMi70} (which was pointed out by
Tsukiyama et al \cite{TsIdAvSh77}). The algorithm of Gerhards and
Lindenberg \cite{GeLi79} started with partial cliques related to
fixed vertices of $G$. Then, cliques were generated from these
partial cliques. Their computational results suggested their
proposed algorithm was as efficient as that of Bron and Kerbosch
\cite{BrKe73} for general graphs, but more efficient on sparse
graphs.

In 1980's, other proposed algorithms include the algorithms of Loukakis
and Tsouros \cite{LoTs81}, Loukakis \cite{Lou83}, Chiba and Nishizeki
\cite{ChNi85}, Tomita et al \cite{ToTaTa88}, and Johnson et al
\cite{JoYaPa88}.

Loukakis and Tsouros \cite{LoTs81} proposed a depth-first
enumerative algorithm that generated all maximal independent sets
lexicographically. They compared their algorithm with the algorithm
of Bron and Kerbosch \cite{BrKe73}, and the algorithm of Tsukiyama
et al \cite{TsIdAvSh77}. Their computational results on graphs of up
to 220 vertices suggested the superior efficiency of their
algorithm. Namely, their algorithm was two to fifteen times faster
than that of Bron and Kerbosch \cite{BrKe73}, and three times faster
than that of Tsukiyama et al \cite{TsIdAvSh77}. Two years later,
Loukakis \cite{Lou83} claimed an additional improvement of three
folds of time saving over Loukakis and Tsouros \cite{LoTs81}.
Loukakis \cite{Lou83} tested his algorithm on graphs of 30 to 220
vertices and 10\% (for small graphs) to 90\% (for large graphs)
densities.

In 1988, Johnson et al \cite{JoYaPa88} proposed an algorithm that
enumerated all maximal independent sets in lexicographic order. The
algorithm has an $O(n^{3})$ delay between the generation of two
subsequent independent sets. Based on one of their result given
below (see \cite{JoYaPa88}), they also showed the nonexistence of
a polynomial-delay algorithm for enumerating maximal cliques in
reverse lexicographic order (if $P \neq NP$). 


\begin{thm}
{\em (\cite{JoYaPa88})} Given a graph G and a maximal independent
set S, it is co$NP$-complete to prove whether S is the
lexicographically last maximal independent set of G.
	\label{thm31}
\end{thm}

Chiba and Nishizeki's \cite{ChNi85} algorithm lists all cliques with
time complexity of $O(a(G)m\mu)$, where $a(G)$ is the
{\em arboricity} of graph G. This is an improvement over the time
complexity of Tsukiyama et al \cite{TsIdAvSh77}.

Finally, Tomita et al \cite{ToTaTa88} proposed a modified Bron and
Kerbosch \cite{BrKe73} algorithm and claimed its time complexity to
be $O(3^{n/3})$. As they pointed out, this was the best one could
hope for since the Moon and Moser graphs \cite{MoMo65} have
$3^{n/3}$ maximal cliques.

\section{Exact Algorithms for the Unweighted Case}

If our goal is to find a maximum clique or just the size of a
maximum clique, a lot of work can be saved in the above
enumerative algorithms. Because once we find a clique, we only need
to enumerate cliques better than the current best clique. Modifying
the enumerative algorithms based on this argument results in various
implicit enumerative algorithms. This argument can also be used in
designing implicit enumerative algorithms. 


The most well known and commonly used implicit enumerative method
for the maximum clique problem is the {\em branch and bound} method.
Background information on how branch and bound method works can be found
in, for example, \cite{BaTo85} and \cite{NeWo88}. The key issues in
a branch and bound algorithm for the maximum clique problem are:

1. How to find a good lower bound, i.e. a clique of large size?

2. How to find a good upper bound on the size of maximum clique?

3. How to branch, i.e., break a problem into smaller subproblems?

Implicit enumerative algorithms for the maximum clique/independent
set problem started in the 1970's by Desler and Hakimi \cite{DeHa70},
Tarjan \cite{Tar72}, and Houck \cite{Hou74}. These early works were
improved in 1977 by Tarjan and Trojanowski \cite{TaTr77}, and by
Houck and Vemuganti \cite{HoVe77}. In Tarjan and Trojanowski
\cite{TaTr77}, they proposed a recursive algorithm for the maximum
independent set problem. They showed their algorithm had a time
complexity of $O(2^{n/3})$. This time bound illustrated that it was
possible to solve a $NP$-complete problem much faster than the
simple, enumerative approach. In the same year, Chv\'{a}tal
\cite{Chv77} showed that using a certain type of {\em recursive
proofs} (see \cite{Chv77}) to show the upper bound on the stability
number ``has length at least $O(c^{n})$'', where $c > 1$ is a
constant. The work of Houck and Vemuganti \cite{HoVe77} exploited
the relationship between the maximum independent set and a special
class of bipartite graphs. They used this relationship to find an
initial solution in their algorithm for the maximum independent set
problem.

Most algorithms in the literature for the maximum clique/independent
set problem were proposed in the 1980's. For example, in 1982,
Loukakis and Tsouros \cite{LoTs82} proposed a {\em tree search}
algorithm that finds the size of a maximum independent set. Then in
1984, Ebenegger et al \cite{EbHaWe84} proposed another algorithm for
finding the stability number of a graph. Their approach is based on
the relationship between the maximization of a pseudo-Boolean
function and the stability number of a graph. Computational tests on
graphs with up to 100 vertices were reported in Ebenegger et al
\cite{EbHaWe84}.

One of the most important contribution in the 1980's on practical
algorithms for the maximum clique problem is due to Balas and Yu
\cite{BaYu86}. In their algorithm, the implicit enumeration was
implemented in a new way. The idea of their approach is as follows.
First, find a maximal induced triangulated subgraph $T$ of $G$. Once
$T$ is found, find a maximum clique of $T$. This clique provides a
lower bound and a feasible solution to the maximum clique problem.
Then, they used a heuristic coloring procedure to extend $T$ to a
larger (maximal) subgraph that had no clique better than the current
best clique. The importance of this second step is that it helps to
reduce the number of subproblems generated from each node of the
search tree, which in turn, reduces the size of the whole search
tree. They solved the maximum clique problem on graphs of up to 400
vertices and 30,000 edges. Comparing their algorithm with other such
algorithms, they found their algorithm not only generated a smaller
search tree, but also required less CPU times.

In 1986, Kikusts \cite{Kik86} proposed a branch and bound algorithm
for the maximum independent set problem based on a new recursive
relation for the stability number of a graph $G$. Namely,
\begin{equation}
\alpha(G) = max\{1 + \alpha(G-v-N(v)), \; \alpha_v' \},
	\label{Krecur}
\end{equation}
where $\alpha_v' = max\{|I|\ | \ I \subseteq G-v$ is independent,
$|I \cap N(v)| \geq 2\}$. This relation is different from the
recursive relation
\begin{equation}
\alpha(G) = max\{1+\alpha(G-v-N(v)), \; \alpha(G-v)\},
	\label{Trecur}
\end{equation}
traditionally used in designing branch and bound algorithms for the
maximum independent set problem. Intuitively, relation
(\ref{Krecur}) is stronger than relation (\ref{Trecur}). However,
the trade off is a more complicated situation in (\ref{Krecur}).
Some computational results were provided in \cite{Kik86} without
comparing with other algorithms.

Also in 1986, Robson \cite{Rob86} proposed a modified recursive
algorithm of Tarjan and Trojanowski \cite{TaTr77}. Robson showed
through a detailed case analysis that his algorithm had a time
complexity of $O(2^{0.276n})$. This is an improvement over the time
complexity $O(2^{n/3})$ of Tarjan and Trojanowski \cite{TaTr77}.
Here we want to mention the complexity proof of a similar recursive
algorithm by Wilf \cite{Wil86.2}. Although Wilf's complexity of
$O(1.39^{n})$ is not as tight as that of Tarjan and Trojanowski
\cite{TaTr77}, his proof is much simpler. Also in \cite{Wil86.2},
Wilf proved (under certain probabilistic assumptions) that the
average number of independent sets in a graph with $n$ vertices
is given by:
\begin{equation}
I_n = \sum ^{n}_{k = 0} \left ( \begin{array}{c}
				n \\ k
				\end{array}
			\right)
		2^{-k(k-1)/2}.
	\label{avst}
\end{equation}
Using (\ref{avst}), it can be shown that the average complexity of a
back tracking algorithm for the maximum independent set problem is
subexponential (because $I_n$ grows at the rate of $O(n^{\log n})$).

In the late 1980's, new algorithms were proposed by Pardalos and Rodgers
\cite{PaRo92} (published in 1992), Gendreau et al \cite{GeSaSo89}
\cite{GePiZu88}, and Tomita et al \cite{ToKoTa88}. The algorithm of
Pardalos and Rodgers \cite{PaRo92} was based on an unconstrained
quadratic zero-one programming formulation of the maximum clique
problem. In their work, the merit of two different branching rules,
{\em greedy} and {\em nongreedy}, were tested. Some interesting
results concerning the behavior of algorithms using these different
rules were reported. The Gendreau et al \cite{GeSaSo89} algorithm
was an implicit enumerative algorithm. Its branching rule (the
selection of the next vertex to branch) is based on the number of
triangles a vertex belongs to. The algorithm of Tomita et al
\cite{ToKoTa88} used a greedy coloring algorithm to get an upper
bound on the size of the maximum clique. Some computational results
could be found in \cite{GeSaSo89} and \cite{ToKoTa88}.

In 1990, more algorithms were proposed. For example, the algorithms
of Pardalos and Phillips \cite{PaPh90}, Friden et al
\cite{FrHeWe90}, Carraghan and Pardalos \cite{CaPa90.1}, Babel and
Tinhofer \cite{BaTi90}.

Pardalos and Phillips \cite{PaPh90} formulated the maximum clique
problem as an indefinite quadratic global optimization problem with
linear constrains. They were able to provide some theoretical upper
bounds on the size of the maximum clique of a graph (see the
paragraph after theorem \ref{thm11} in section 1). The algorithm of
Friden et al \cite{FrHeWe90} was a branch and bound algorithm for
the maximum independent set problem. They used the Tabu search
technique in finding lower and upper bounds in their algorithm.

Carraghan and Pardalos \cite{CaPa90.1} proposed an implicit
enumerative algorithm. Their algorithm is very easy to understand
and very efficient for sparse graphs. Their
branching rule corresponds to the {\em nongreedy} rule described in
Pardalos and Rodger's \cite{PaRo92}. Using this algorithm, they were
able to solve problems on graphs of 500 vertices. They have also
tested their algorithm on instances of graphs with 1000 and 2000
vertices. Since the algorithm is easy to understand and their actual
code is available, it can serve as a benchmark for comparing
different algorithms.

Babel and Tinhofer \cite{BaTi90} proposed a branch and bound
algorithm for the maximum clique problem. The main ingredient of
their algorithm is the use of a fast and relatively good heuristic
for the minimum coloring problem proposed by Brelaz \cite{Bre79}.
The coloring heuristic is called the {\em degree of saturation
largest first} (DSATUR). Applying DSATUR to a graph, one can find an
upper bound on the size of the maximum clique as well as a maximal
clique (thus, a lower bound). Babel and Tinhofer exploited this
distinct feature and applied DSATUR at each node of the search tree.
They tested their algorithm on graphs of 100 to 400 vertices with
varying densities. In 1991, Babel \cite{Bab91} further refined and
improved the algorithm of Babel and Tinhofer \cite{BaTi90}. 



\section{Exact Algorithms for the Weighted Case}

Algorithms for finding a maximum weight independent set of an
arbitrary graph started in 1975 by Nemhauser and Trotter
\cite{NeTr75}. They considered the polyhedron relationships between
the edge formulation (\ref{mcef}) of the maximum weight independent
set problem and its linear relaxation problem. Their main results
were given as theorem \ref{thm01} in section 1 of the
present paper. Based on this result, they proposed an algorithm for
the maximum weight independent set problem.

In 1977, Balas and Samuelsson \cite{BaSa77} proposed an algorithm
that solved the minimum vertex covering problem (a weighted version
was available as mentioned \cite{BaSa77}). Their algorithm was based
on the relationship between the integer dual feasible solution and
an equivalent linear programming for the vertex covering problem.
Labeling procedures were designed to generate and improve vertex
covers. When these labeling procedures could not continue, branch
and bound was used. The computational tests in \cite{NeTr75} and
\cite{BaSa77} were conducted on unweighted graphs of up to 50
vertices. 


In 1983, Loukakis and Tsouros \cite{LoTs83} proposed an algorithm
for the maximum weight independent set problem.
It seems that almost nothing else appeared in the literature
until late 1980's and early 1990's.  Recently
published algorithms we are aware of for the maximum weight
clique/independent set problem are due to Pardalos and Desai
\cite{PaDe91}, Balas and Xue \cite{BaXu91}, and Nemhauser and
Sigismondi \cite{NeSi92}.

The algorithm proposed by Pardalos and Desai \cite{PaDe91} was based
on an unconstrained quadratic 0-1 formulation of the maximum weight
independent set problem. In addition,
they established an interesting relationship between
the local minima of the quadratic problem and the maximal
independent sets of a graph as follows:
\begin{thm}
$x$ is a discrete local minimum for problem {\em (\ref{Clique:6})}
if and only if $x$ represents a maximal independent set of $G$.
	\label{thm5.1}
\end{thm}
Their algorithm (for maximum weight independent set) used the {\em
nongreedy} search strategy described in Pardalos and Rodgers
\cite{PaRo92}. With this algorithm they were able to solve problems of up to 500
vertices with different densities. Here we want to mention an
unpublished work by Carraghan and Pardalos that was the weighted
version of the Carraghan and Pardalos \cite{CaPa90.2} algorithm. As
its unweighted version, it is also very simple to understand.
Computational tests shown that the weighted version of Carraghan and
Pardalos algorithm is more efficient than that of Pardalos and Desai
\cite{PaDe91}.

The Balas and Xue \cite{BaXu91} algorithm extended the algorithm of
Balas and Yu \cite{BaYu86} to the weighted case. To do that, a
minimum weighted coloring of a triangulated graph was needed.
Although the minimum weighted coloring problem on triangulated
graphs is known to be in class $P$ (see \cite{Gol80}), there was no
algorithm in the literature that had reasonable time complexity.
Balas and Xue \cite{BaXu91} proposed a combinatorial algorithm
for this problem with a time complexity of $O(n^{2})$. With this
algorithm, they extended the Balas and Yu algorithm to the weighted
case. Their computational results showed that the size of the search
tree was greatly reduced and the CPU time was much smaller than
other such algorithms, especially for large, dense graphs. Graphs of
size up to 2000 vertices were solved on a workstation.

The algorithm of Nemhauser and Sigismondi \cite{NeSi92} used the
polyhedron approach. They tried to solve the problem by first
solving the linear relaxation of the corresponding integer
programming problem. If the optimal solution to the relaxation
problem was integer, it was done. Otherwise, sets of valid
inequalities were generated and added into the relaxed problem to
cut off the current fractional solution. They restricted themselves
to some classes of facet defining inequalities for the maximum
independent set problem. Since not all facets for the
clique/independent set polytope are known, there was no guarantee
that a fractional solution would always be cut off. When this
happened, they switched to branch and bound method. From their
computational test, they found too many iterations in solving the
linear relaxation problems. The largest graphs they tried to solve
had up to 120 vertices. 



\section{Heuristics}

In a branch and bound algorithm for the maximum clique problem, its
lower bounding procedure usually provides a maximal clique which can
be used to approximate the maximum clique of $G$. Since different
branch and bound algorithms tend to have different bounding
procedures, they provide us different heuristics for the maximum
clique problem. On the other hand, there are many heuristics in the
literature designed to find an approximation solution to the maximum
clique problem. These heuristics are usually more complicated than
the lower bounding procedures from a branch and bound algorithm. The
reason is that they will be run only once. 


The majority of approximation algorithms in the literature for the
maximum clique problem are called {\em sequential greedy heuristics}.
These heuristics generate a maximal clique through the
repeated addition of a vertex into a partial clique, or the repeated
deletion of a vertex from a set that is not a clique.

Kopf and Ruhe \cite{KoRu87} named these two classes of heuristics
the {\em Best in} and the {\em Worst out} heuristics. Decisions on
which vertex to be {\em added in} or {\em moved out} next are based
on certain indicators associated with candidate vertices. For
example, a possible {\em Best in} heuristic constructs a maximal
clique by repeatedly {\em adding in} a vertex that has the largest
degree among candidate vertices. In this case, the indicator is the
degree of a vertex. On the other hand, a possible {\em Worst out}
heuristic can start with the whole vertex set $V$. It will
repeatedly remove a vertex out of $V$ until $V$ becomes a clique.

Kopf and Ruhe \cite{KoRu87} further divided the above two classes of
heuristics into {\em New} and {\em Old} ({\em Best in} or {\em Worst
out}) heuristics. Namely, if the indicators are updated every time a
vertex is added in or moved out, then the heuristic is called a {\em
New} heuristic. Otherwise it is called an {\em Old} heuristic. We
can find in the literature that most heuristics for the maximum
clique problem fall in one or the other classes. See for example, the
approximation algorithm of Johnson \cite{Joh74}, and the
approximation algorithm of Tomita et al \cite{ToMiTa88}. The
differences among these heuristics are their choice of indicators
and how indicators are updated. A heuristic of this type can run
very fast.

A common feature of the sequential heuristics is that they all
find only one maximal clique. Once a maximal clique is found, the
search stops. We can view this type of heuristics from a different
point of view. Let us define $S_G$ to be the space consisting of all
the maximal cliques of $G$. What a sequential greedy heuristic does
is to find one point in $S_G$, hoping it is (close to) the optimal
point. This suggests us a possible way to improve our approximation
solutions, namely, expand the search in $S_G$. For example, once we
find a point $x \in S_G$, we can search its neighbors to improve
$x$. This leads to the class of the {\em local search heuristics}.

In a local search heuristic, the more neighbors of $x \in S_G$ we
search, the greater chance of finding a better solution. Depending
on the neighborhood definition of a point $x \in S_G$, and how the
search is performed, different local search heuristics result. A
well known class of local search heuristics in the literature is the
{\em k-interchange} heuristics. They are based on the {\em
k-neighbor} of a feasible solution. In the case of the maximum
clique problem, a k-neighbor of $x \in S_G$ is defined as follows.
Let $y \in S_G$, $y$ is a k-neighbor of $x$ if $|x-y| \leq k$, where
$k \leq |x|$. A k-interchange heuristic first finds a maximal clique
$x \in S_G$. Then it searches all the k-neighbors of $x$ and outputs
the best clique found. As one will expect, the main factors for the
complexity of this class of heuristics are the size of the
neighborhood and the searches involved. For example, in the
k-interchange heuristic, the complexity grows roughly with
$O(n^{k})$. 


The solution quality of a local search heuristic directly depends on
the starting point $x \in S_G$ and the neighborhood of $x$. To
improve the quality of its solution, we need to increase the
neighborhood of $x$ (the starting point) to include a ``better''
point. When we want to look for various points spread over $S_G$, we
need to have a very large neighborhood. The problem with this is
when the size of the neighborhood increases, the search effort
increases so rapidly that one could not afford it. 


A class of heuristics designed to search various points of $S_G$ is
called the {\em randomized heuristics}. The main ingredient of this
class of heuristics is the part that finds a random point in $S_G$.
A possible way to do that is to include some random factors in the
generation of a point of $S_G$. A randomized heuristic runs a
heuristic (with random factors included) a number of times to find
different points over $S_G$. For example, we can randomize a
sequential greedy heuristic and let it run $N$ times. The complexity
of a randomized heuristic depends on the complexity of the heuristic
and the number $N$.

An elaborated implementation of the randomized heuristic for the
maximum independent set problem can be found in Feo et al
\cite{FeReSm90} where local search is combined with randomized
heuristic. Their computational results indicated that their approach
was effective in finding large cliques of randomly generated graphs.
For example, for randomly generated graphs with 1000 vertices and
50\% density, their approach found cliques of size 15 or larger in
most cases. Here, 15 is a bound derived from the probabilistic analysis
of this class of graphs (see \cite{Bol85}, \cite{BoEr76},
\cite{Fri90}). A different implementation of a randomized
algorithm for the maximum independent set problem can be found in
\cite{AlBaIt86}.

Recently, Tabu search and Neural Networks have also been used to find
an approximate solution for the maximum clique problem. For
example, Friden et al \cite{FrHeWe89} proposed a heuristic based on
Tabu search technique. A different implementation of Tabu search for
the same problem was proposed by Gendreau et al \cite{GeSaSo89}.
Ramanujam and Sadayappan \cite{RaSa88} proposed a heuristic based on
Neural Networks. What these methods accomplished is to search
various points of $S_G$. However, since there are too many
parameters affecting the search pattern (and the result), it is hard
to tell what points in $S_G$ are being searched. Some computational
results from these methods are encouraging. 


Another type of heuristics that finds a maximal clique of $G$ is
called the {\em subgraph approach} (see \cite{BaYu86}). It is based
on the fact that a maximum clique $C$ of a subgraph $G' \subseteq G$
is also a clique of $G$. The subgraph approach first finds a
subgraph $G' \subseteq G$ such that the maximum clique of $G'$ can
be found in polynomial time. Then it finds a maximum clique of $G'$
and use it as the approximation solution. The advantage of this
approach is that in finding the maximum clique $C \subseteq G'$, one
has (implicitly) searched many other cliques of $G'$ ($S_{G'}
\subseteq S_G$). Because of the special structure of $G'$, this
implicit search can be done efficiently. In Balas and Yu
\cite{BaYu86}, $G'$ is a maximal induced triangulated subgraph of
$G$. Since many classes of graphs have polynomial algorithms for the
maximum clique problem, the same idea also applies there. For
example, the class of edge-maximal triangulated subgraphs was chosen
in \cite{Xue91} (also see \cite{Bal86}).

Additional heuristics for the maximum clique/independent set and
related problems on arbitrary or special class of graphs can be
found in \cite{ChNiSa83}, \cite{ChNa91}, \cite{Chv79},
\cite{FiWo82}, \cite{TaChLeHu90}.

\section{Applications}

Practical applications of the maximum clique and related problems
include project selection, classification theory, fault tolerance,
coding theory, computer vision, economics, information retrieval,
signal transmission theory, aligning DNA and protein sequences,
and other specific problems. Some of these applications can be
found in \cite{Avo62}, \cite{BaBr82}, \cite{BaWeEp92},
\cite{BePe90}, \cite{Chr75}, \cite{Deo74}, \cite{LeMuAb89},
\cite{Lov79}, \cite{MaSl79}, \cite{Miller92}, \cite{ReNiDe77},
\cite{Slo89}, \cite{VinArg91}, \cite{VinArg92} and \cite{WiPiFe87}.

Next we provide some very interesting applications of the maximum
clique problem. In addition, some problems arising in these
applications can be used as test problems for algorithm comparison
and correctness. 


We start with an application in computing binary (constant weight)
codes \cite{BrShSlSm90}. Let $A(n,d,w)$ be the maximal number of
binary vectors of length $n$, with Hamming distance at least $d$
apart, and constant weight $w$. Also let $A(n,d)$ be the maximal
possible number of binary vectors of length $n$ and Hamming distance
at least $d$ apart (with no restriction on weight).

To compute $A(n,d)$ or $A(n,d,w)$ one forms the graph with $2^n$ or
${n\choose w}$ vertices, corresponding to all possible code-words,
joins two vertices by an edge if their Hamming distance is at least
$d$, and finds the maximum clique. Similarly, finding the largest
code invariant under a given permutation group, requires finding the
maximum clique in a graph with weights attached to the vertices.

The exact values of $A(n,d,w)$ are known for all $n \leq 11$ (the
first undetermined values being $80 \leq A(12,4,5) \leq 84$).
Similarly, for $d$ even, $A(n,d)$ is known exactly for $n \leq 10$
(the first undetermined values being $72 \leq A(11,4) \leq 79$). For
more details and other references see the paper by Brouwer et al
\cite{BrShSlSm90}.

The next application occurs in geometry \cite{Ste74}. Minkwoski
conjectured that all extremal lattices for the supremum norm were of
a certain simple form, and observed that this conjecture had a
simple geometric interpretation, that is, in any tiling of $R^n$
with unit $n$-cubes, there must exist two cubes having a complete
facet in common. A family of cubes whose interiors are disjoint and
whose union is $R^n$ is called a tiling. If the centers of the cubes
form a lattice, then we have a lattice tiling. Although Minkowski's
conjecture was proved in 1942, Keller generalized it to conjecture
that any tiling in $R^n$ by unit $n$-cubes contains two cubes having
a complete facet in common. Corradi and Szabo \cite{CoSz90} proved
that there is a counterexample to this conjecture if and only if the
following graphs $\Gamma_n$ (of $4^{n}$ vertices) has a $2^n$ size
maximum clique. The $4^n$ vertices of $\Gamma_n$ are $n$-tuples of
integers $0,1,2$ and $3$. A pair of these $n$-tuples are adjacent if
there is a position at which the corresponding components are $2$
modulo $4$ and if there is a further position at which the
corresponding components are different. The conjecture was proved by
Peron \cite{Per40} to be true for $n \leq 6$ and was proved by
Lagarias and Shor \cite{LaSh92} to be false for $n \geq 10$. The
conjecture remains open for the values of $n$ equal to $7,8,9$.

Another interesting application appears in the study of assignment
polytopes (see the paper by S. Onn, \cite{Onn92}). In particular,
consider the assignment polytope $P(n-1,1)$. The $1$-skeleton of $P$
is the graph of the set of vertices of $P$ in which the edges are
the $1$-faces of $P$. Onn proved that large independent sets in the
$1$-skeleton of $P$ are exhibited, by proving that its stability
number is $2^{\Omega (\sqrt{n} \log n)}$.
More details on these applications and computational results with
exact algorithms will appear in an upcoming paper \cite{HPV92}.

\section{Concluding Remarks}

While a variety of algorithms and heuristics have been proposed for 
the solution of the maximum clique problem, only a few of the
suggested algorithms have been programmed and tested on graphs where
the problem is difficult to solve. Extensive computational results 
are needed to evaluate the average performance of the algorithms,
not only on randomly generated graphs but also on problems from a 
diverse spectrum of applications.

In this bibliographic survey, we have attempted to briefly summarize
the main ideas in each of the proposed algorithms. Many applications
and algorithms on problems related to the maximum clique problem can
be found in the list of references below.

%

\begin{thebibliography}{10}

\bibitem{AhErLi88}
R.~Aharoni, P.~Erd\"{o}s and N.~Linial,
\newblock Optima of dual integer linear programs,
\newblock {\em Combinatorica}, Vol. 8, No. 1, 13-20, 1988.

\bibitem{AlBaIt86}
N.~Alon, L.~Babai and A.~Itai,
\newblock A Fast and Simple Randomized Parallel Algorithm for the
Maximal Independent Set Problem,
\newblock {\em J. Algorithms}, 7: 567-583, 1986.

\bibitem{Akk73}
E.A.~Akkoyunlu,
\newblock The Enumeration of Maximal Cliques of Large Graphs,
\newblock {\em SIAM Journal on Computing}, 2: 1-6, 1973.

\bibitem{AlHu78}
M.O.~Albertson and J.P.~Hutchinson,
\newblock On the Independence Ratio of a Graph,
\newblock {\em J. Graph Theory}, 2: 1-8, 1978.

\bibitem{AmHa72}
A.T.~Amin and S.L.~Hakimi,
\newblock Upper Bounds on the Order of a Clique of a Graph,
\newblock {\em SIAM J. of Appl. Math.}, 22, No. 4: 569-573, 1972.

\bibitem{ArLuMo92}
S.~Arora, C.~Lund, R.~Motwani, M.~Sudan and M.~Szegedy,
\newblock On the intractability of approximation problems,
\newblock {\em Preliminary Draft, University of Rochester, NY},
1992.

\bibitem{ArSa92}
S.~Arora and S.~Safra,
\newblock Approximating the maximum clique is $NP$-complete,
\newblock {\em Preliminary Draft, University of Rochester, NY},
1992.

\bibitem{Avo62}
G.~Avondo-Bodeno,
\newblock {\em Economic Applications of the Theory of Graphs},
\newblock Gordon and Breach, Science Publishers, New York, 1962.

\bibitem{AuMi70}
J.G.~Auguston and J.~Minker,
\newblock An Analysis of Some Graph Theoretical Cluster
Techniques,
\newblock {\em J. Assoc. Comput. Mach.}, 17: 571-588, 1970.

\bibitem {AuAtPr80}
G.~Ausiello, A.~D'Atr and M.~Protasi,
\newblock Structure Preserving Reductions among	Convex Optimization
Problems,
\newblock {\em J. Comput. and Syst. Sci.}, 21: 136-153, 1980.

\bibitem{BaBoVer88}
S.M.~Baas, M.C.~Bonvanie and A.J.~Verschoor,
\newblock A Relaxation Method for the Set Packing Problem Using
Polyhedron Characteristic,
\newblock {\em Technical Report 699}, University of Twente,
Netherlands, 1988.

\bibitem{Bab91}
L.~Babel,
\newblock Finding Maximum Cliques in Arbitrary and in Special Graphs,
\newblock {\em Computing}, 46: 321-341, 1991.

\bibitem{BaTi90}
L.~Babel and G.~Tinhofer,
\newblock A Branch and Bound Algorithm for the Maximum Clique  
Problem,
\newblock {\em ZOR-Methods and Models of Operations Research}, 34:
207-217, 1990.

\bibitem{Bal86}
E.~Balas,
\newblock A Fast Algorithm for Finding an Edge-Maximal Subgraph with
a TR-Formative Coloring,
\newblock {\em Discr. Appl. Math.}, 15: 123- 134, 1986.

\bibitem{BaChNe87}
E.~Balas, V.~Chv\'{a}tal and J.~Ne\u{s}etril, 
\newblock On the maximum weight clique problem,
\newblock {\em Math. of Operations Research}, Vol. 12, No. 3,
522-535, 1987.

\bibitem{BaSa77}
E.~Balas and H.~Samuelsson,
\newblock A Node Covering Algorithm,
\newblock {\em Naval Research Logistics Quarterly}, 24: 213-233,
1977.

\bibitem{BaTo85}
E.~Balas and P.~Toth,
\newblock Branch and Bound Methods, In:
\newblock In Lawler, Lenstra, RinnooyKan, and Shmoys (eds.),
{\em The Traveling Salesman Problem: A Guided Tour of Combinatorial
Optimization}, Wiley, 361-403, 1985.

\bibitem{BaXu91}
E.~Balas and J.~Xue,
\newblock Minimum Weighted Coloring of Triangulated Graphs, with
Application to Maximum Weight Vertex Packing and Clique Finding in
Arbitrary Graphs,
\newblock {\em SIAM J. Comput.} Vol. 20, No. 2: 209-221, 1991.

\bibitem{BaYu86}
E.~Balas and C.S.~Yu,
\newblock Finding a Maximum Clique in an Arbitrary Graph,
\newblock {\em SIAM J. Computing}, 14, No. 4: 1054-1068, 1986.

\bibitem{BaYu89}
E.~Balas and C.S.~Yu,
\newblock On Graphs with Polynomially Solvable Maximum-Weight Clique
Problem,
\newblock {\em Networks}, 19: 247-253, 1989.

\bibitem{BaBr82}
D.H.~Ballard and M.~Brown,
\newblock {\em Computer Vision},
\newblock Prentice-Hall, Englewood Cliffs, N.J. 1982.

\bibitem{BaEv83}
R.~Bar-Yehuda and S.~Even,
\newblock A $2-\frac{\log \log n/2}{\log n}$ performance ratio for
the weighted vertex cover problem,
\newblock {\em Technical Report 260}, Technion, Haifa, Jan. 1983

\bibitem{BaWeEp92}
F.~Barahona, A.~Weintraub, and R.~Epstein,
\newblock Habitat dispersion in forest planning and the stable set
problem,
\newblock {\em Operations Research} 40, Supp. 1: S14-S21, 1992.

\bibitem{BeTa66}
A.R.~Bednarek and O.E.~Taulbee,
\newblock On maximal chains,
\newblock{\em Roum. Math. Pres et Appl.}, 11: 23-25, 1966.

\bibitem{Bei69}
L.W.~Beineke,
\newblock A Survey of Packings and Coverings in Graphs in the Many
Facets of Graph Theory,
\newblock G.~Chartrand and S.~Kapoor (eds.), Springer-Verlag, 45-53,
1969.

\bibitem{BeCh84}
C.~Berge and V.~Chv\'{a}tal (eds.),
\newblock Topics on Perfect Graphs,
\newblock {\em Annals of Discrete Mathematics}, 21, 1984.

\bibitem{BePe90}
P.~Berman and A.~Pelc,
\newblock Distributed Fault Diagnosis for Multiprocessor Systems
\newblock {\em Proc. of the 20th Annual Intern. Symp. on
Fault-Tolerant Computing} (Newcastle, UK), 340-346, 1990.

\bibitem{BeSc89}
P.~Berman and G.~Schnitger,
\newblock On the complexity of approximating the independent set
problem,
\newblock In {\em Proceedings of the 1989 Symposium on Theoret.
Aspects of Comp. Sci.}, Springer-Verlag, Lecture Notes in Computer
Sciences 349: 256-268, 1989.

\bibitem{Bil81}
A.~Billionnet,
\newblock An Upper Bound on the Size of the Largest Cliques in a
Graph,
\newblock {\em J. Graph Theory}, 5:165-169, 1981.

\bibitem{BoEr76}
B.~Bollob\'{a}s and P.~Erd\"{o}s,
\newblock Cliques in Random Graphs,
\newblock {\em Math. Proc. Cambridge Philos. Soc.}, 80: 419-427,
1976.

\bibitem{Bol85}
B.~Bollob\'{a}s,
\newblock {\em Random Graphs},
\newblock Academic Press, NY, 1985.

\bibitem{Bon64}
R.E.~Bonner,
\newblock On Some Clustering Techniques,
\newblock {\em IBM J. Res. Develop.}, 8: 1, 22-32, 1964.

\bibitem{BoHa90}
R.~Boppana and M.M.~Halld\'{o}rsson,
\newblock Approximating Maximum Independent Sets by Excluding
Subgraphs,
\newblock {\em Proc. SWAT 90}, Lecture Notes in Computer Sciences,
11-25, Springer, 1990.

\bibitem{BoUh79}
M.~Boulala and J.P.~Uhry,
\newblock Polytope des Independants dans un Graphe Serie-Parallele,
\newblock {\em Discrete Mathematics}, 27: 225-243, 1979.

\bibitem{Bre79}
D.~Brelaz,
\newblock New Methods to Color the Vertices of a Graph,
\newblock {\em Comm. of ACM}, 22, No. 4: 251-256, 1979.

\bibitem{BrKe73} 

C.~Bron and J.~Kerbosch,
\newblock Algorithm 457: Finding All Cliques of an Undirected
Graph,
\newblock {\em Comm. of ACM}, 16: 575-577, 1973.

\bibitem{BrShSlSm90} 
A.~E.~Brouwer, J.~B.~Shearer, N.~J.~A.~Sloane and W.~D.~Smith,
\newblock A New Table of Constant Weight Codes,
\newblock {\em J. IEEE Trans. Information Theory}, 36: 1334-1380,
1990.

\bibitem{Buc81}
M.A.~Buckingham,
\newblock Efficient Stable Set and Clique Finding Algorithms for
Overlap Graphs,
\newblock {\em Technical Report} Dept. Computer Science, New York
Univ., 1981.

\bibitem{BuFo84}
M.~Burlet and J.~Fonlupt,
\newblock Polynomial Algorithm to Recongnize a Meyniel Graph,
\newblock W.R. Pulleyblank (ed.), {\em Progress in Combinatorial
Optimization}, Academic Press, Toronto, 69-99, 1984.

\bibitem{Bur89}
J.E.~Burns,
\newblock The Maximum Independent Set Problem for Cubic Planar Graph,
\newblock {\em Networks}, Vol. 9: 373-378, 1989

\bibitem{BuHaHa75}
L.~Butz, P.L.~Hammer and D.~Hausmann,
\newblock Reduction Methods for the Vertex Packing Problem,
\newblock {\em Technical Report 7540}, Univ. of Bonn, Institut
f\"{u}r \OE konometrie und Operations Research, 1975.

\bibitem{CaPa90.1}
R.~Carraghan and P.M.~Pardalos,
\newblock An Exact Algorithm for the Maximum Clique Problem,
\newblock {\em Operations Research Letters}, 9: 375-382, 1990.

\bibitem{CaPa90.2}
R.~Carraghan and P.M.~Pardalos,
\newblock A Parallel Algorithm for the Maximum Weight Clique Problem,
\newblock {\em Technical Report CS-90-40}, Dept. of Computer
Science, Penn. State Univ., 1990.

\bibitem{ChNi85}
N.~Chiba and T.~Nishizeki,
\newblock Arboricity and Subgraph Listing Algorithms,
\newblock {\em SIAM J. Comput.}, 14: 210-223, 1985.

\bibitem{ChNiSa82}
N.~Chiba, T.~Nishizeki and N.~Saito,
\newblock An Approximation Algorithm for the Maximum Independent Set
Problem on Planar Graphs,
\newblock {\em SIAM. J. Comput.}, Vol. 11, No. 4: 663-675, 1982.

\bibitem{ChNiSa83}
N.~Chiba, T.~Nishizeki and N.~Saito,
\newblock An Algorithm for Finding a Large Independent Set in Planar
Graphs,
\newblock {\em Networks}, 13: 247-252, 1983.

\bibitem{Chr75}
N.~Christofides,
\newblock {\em Graph theory, An algorithmic approach},
\newblock Academic Press, 1975.

\bibitem{ChNa91}
M.~Chrobak and J.~Naor,
\newblock An Efficient Parallel Algorithm for Computing a Large
Independent Set in a Planar Graph,
\newblock {\em Algorithmica}, 6: 801-815, 1991.

\bibitem{Chv75}
V.~Chv\'{a}tal,
\newblock On Certain Polytopes Associated with Graphs,
\newblock {\em J. of Combin. Theory B}, 18: 138-154, 1975.

\bibitem{Chv77}
V.~Chv\'{a}tal,
\newblock Determining the Stability Number of a Graph,
\newblock {\em SIAM J. on Comput.}, 6: 643-662. 1977.

\bibitem{Chv79}
V.~Chv\'{a}tal,
\newblock A Greedy Heuristic for the Set-covering Problem,
\newblock {\em Math. Oper. Res.}, 4: 233-23, 1979.

\bibitem{Chv85}
V.~Chv\'{a}tal,
\newblock Perfectly Orderable Graphs,
\newblock {\em Annals of Discrete Math.}, 21: 63-65, 1985.

\bibitem{ChFr86}
E.~Choukhmane and J.~Franco,
\newblock An Approximation Algorithm for the Maximum Independent Set
Problem in Cubic Planar Graphs,
\newblock {\em Networks}, Vol. 16: 349-356, 1986.

\bibitem{ChLe}
R.C.~Chang and H.S.~Lee,
\newblock Finding a Maximum Set of Independent Chords in a Circle,
\newblock {\em Info. Proc. Letters}, 41: 99-102, 1992.

\bibitem{CoSz90}
K.~Corradi and S.~Szabo,
\newblock A Combinatorial Approach for Keller's Conjecture,
\newblock {\em Periodica Mathematica Hungarica}, Vol. 21, No. 2:
95-100, 1990.

\bibitem{CrFiSi91}
P.~Crescenzi, C.~Fiorini and R.~Silvestri,
\newblock A Note on the Approximation of the MAX CLIQUE Problem,
\newblock to appear in {\em Infor. Proces. Letters}, 40: 1-5, 1991.

\bibitem{DaKa87}
E.~Dahlhaus and M.~Karpinski,
\newblock A Fast Parallel Algorithm for Computing All Maximal
Cliques in a Graph and the Related Problems,
\newblock {\em Technical Report 8516-CS}, Institut f\"{u}r
Informatik, Universit\"{a}t Bonn, R\"{o}merstrasse 164, 5300 Bonn 1,
1987.

\bibitem{DeHu75}
V.~Degot and J.M.~Hualde,
\newblock De l'utilisation de la Notion de Clique en Mati\`{e}re de
Typologie des Populations,
\newblock R.A.I.R.O., 1, 1975

\bibitem{Deo74}
N.~Deo,
\newblock {\em Graph Theory with Applications to Engineering and
Computer Science},
\newblock Prentice-Hall, Englewwod Cliffs, NJ, 1974.

\bibitem{DeHa70} J.F.~Desler and S.L.~Hakimi,
\newblock On Finding a Maximum Internally Stable Set of a Graph,
\newblock {\em Proc. of Fourth Annual Princeton Conference on
Information Sciences and Systems}, 4: 459-462, Princeton, NJ, 1970.

\bibitem{Dir52}
G.A.~Dirac,
\newblock A Property of 4-Chromatic Graphs and Some Remarks on
Critical Graphs,
\newblock {\em J. London Math. Society}, 27: 85-92, 1952.

\bibitem{Dir61}
G.A.~Dirac,
\newblock On Rigid Circuit Graphs,
\newblock {\em Abh, Math. Sem.}, Univ. Hamburg, 25: 71-76, 1961.

\bibitem{Dor69}
P.~Doreian,
\newblock A Note on the Detection of Cliques in Valued Graphs,
\newblock {\em Sociometry}, 32: 237-242, 1969.

\bibitem{EbHaWe84}
C.~Ebenegger, P.L.~Hammer, and D.~de~Werra,
\newblock Pseudo-Boolean Functions and Stability of Graphs,
\newblock {\em Annals of Discrete Mathematics}, 19: 83-98, 1984.

\bibitem{Edm62}
J.~Edmonds,
\newblock Covers and Packings in a Family of Sets,
\newblock {\em Am. Math. Soc. Bull.}, 68: 494-497, 1962.

\bibitem{EdEl83}
C.S.~Edwards and C.H.~Elphick,
\newblock Lower Bounds for the Clique and the Chromatic Numbers of a
Graph,
\newblock {\em Disc. Math.}, 5: 51-64, 1983.

\bibitem{ErEr85}
P.~Erd\"{o}s and M.~Erne,
\newblock Clique Numbers of Graphs,
\newblock {\em Discrete Mathematics}, 59: 235-242, 1986.

\bibitem{Esc73}
F.~Escalante,
\newblock \"{U}ber Iterierte Clique-Graphen,
\newblock {\em Abh. Math. Sem. Univ. Hamburg}, 39: 59-68, 1973.

\bibitem{Faj78}
S.~Fajtlowics,
\newblock On the Size of Independent Sets in Graphs,
\newblock {\em Proc. 9th S.E. Conf. on Combin., Graph Theory and
comput.}, 269-274, Boca Raton, 1978.

\bibitem{FeGoLoSaSz91}
U.~Feige, S.~Goldwasser, L.~Lov\'{a}sz, S.~Safra, and M.~Szegedy,
\newblock Approximating the maximum clique is almost $NP$-complete,
\newblock {\em Proc. 32nd IEEE Symp. on Foundations of Computer
Science}, 2-12, 1991.

\bibitem{FeReSm90}
T.A.~Feo, M.G.C.~Resende and S.H.~Smith,
\newblock A Greedy Randomized Adaptive Search Procedure for Maximum
Independent Set,
\newblock {\em Technical Report}, Univ. of Texas, Austin, 1990.

\bibitem{FiWo82}
M.L.~Fisher and L.A.~Wolsey,
\newblock On the Greedy Heuristic for Continuous Covering and
Packing Problems,
\newblock {\em SIAM J. Alg. Disc. Meth.}, 3: 584-591, 1982.

\bibitem{Fra76}
A.~Frank,
\newblock Some Polynomial Algorithms for Certain Graphs and
Hypergraphs,
\newblock {\em Proc. 5th British Combin. Conf.}, 211-226, 1976.

\bibitem{FrHeWe89}
C.~Friden, A.~Hertz, and D.~de~Werra,
\newblock Stabulus: A Technique for Finding Stable Sets in Large
Graphs with Tabu Search,
\newblock {\em Computing}, 42: 35-4, 1989.

\bibitem{FrHeWe90}
C.~Friden, A.~Hertz and M.~de~Werra,
\newblock TABARIS: An Exact Algorithm Based on Tabu Search for
Finding a Maximum Independent Set in a Graph,
\newblock {\em Computers and Operations Research}, 17, No. 5:
437-445, 1990.

\bibitem{Fri90}
A.~Frieze,
\newblock On the Independence Number of Random Graphs,
\newblock {\em Discrete Math.}, 81: 171-175, 1990.

\bibitem{Fur87}
Z.~F\"{u}redi,
\newblock The Number of Maximal Independent Sets in Connected Graphs,
\newblock {\em J. Graph Theory}, 11: 463-470, 1987.

\bibitem{GaJo79}
M.~Garey and D.~Johnson,
\newblock {\em Computers and Intractability, A guide to the Theory of
$NP$-Completeness},
\newblock FREEMAN, San Francisco, 1979

\bibitem{Gav72}
F.~Gavril,
\newblock Algorithms for Minimum Colouring, Maixmum Clique, Minimum
Covering by Cliques, and Maximum Independent Set of a Chordal Graph,
\newblock {\em SIAM J. Comput.}, 1: 180-187, 1972.

\bibitem{Gav73}
F.~Gavril,
\newblock Algorithms for a Maximum Clique and a Maximum Independent
Set of a Circle Graph,
\newblock {\em Networks}, 3: 261-273, 1973.

\bibitem{Gav74}
F.~Gavril,
\newblock Algorithms on Circular Arc Graphs,
\newblock {\em Networks}, 4:357-369, 1974.

\bibitem{GePiZu88}
M.~Gendreau, J.C.~Picard and L.~Zubieta,
\newblock An Efficient Implicit Enumeration Algorithm for the
Maximum Clique Problem,
\newblock A. Kurzhanski et al. (eds), {\em Lecture Notes in
Economics and Mathematical Systems}, 304: 70-91, Springer-Verlag,  
1988. 


\bibitem{GeSaSo89}
A.~Gendreau, L.~Salvail, and P.~Soriano,
\newblock Solving the Maximum Clique Problem Using a Tabu Search
Approach,
\newblock {\em Technical Report 675}, Center for Research on
Transportation, University of Montreal, Montreal, Canada, 1989.

\bibitem{GeSc86}
A.M.H.~Gerards and A.~Schrijver,
\newblock Matrices with the Edmonds-Johnson Property,
\newblock {\em Combinatorica}, 6: 403-417, 1986.

\bibitem{GeLi79}
L.~Gerhards and W.~Lindenberg,
\newblock Clique Detection for Nondirected Graphs: Two New
Algorithms,
\newblock {\em Computing}, 21: 295-322, 1979.

\bibitem{GiTr81}
R.~Giles and L.R.~Trotter,
\newblock On Stable Set Polyhedra for $K_{1,3}$ Free Graphs,
\newblock {\em J. Combin. Theory B}, 31: 313-326, 1981.

\bibitem{GoSp89.1}
M.~Goldberg and T.~Spencer,
\newblock A New Parallel Algorithm for the Maximal Independent Set
Problem,
\newblock {\em SIAM J. Comput.}, Vol. 18, No. 2: 419-427, 1989.

\bibitem{GoSp89.2}
M.~Goldberg and T.~Spencer,
\newblock Constructing a Maximal Independent Set in Parallel,
\newblock {\em SIAM J. Disc. Math.}, Vol. 2, No. 3: 322-328, 1989.

\bibitem{GoHa90}
M~.Goldmann and J.~Hastad,
\newblock A Simple Lower Bound for Monotone Clique Using a
Communication Game,
\newblock {\em Info. Proc. Letters}, 41: 221-226, 1992.

\bibitem{Gol80}
M.C.~Golumbic,
\newblock {\em Algorithmic Graph Theory and Perfect Graphs},
\newblock Academic Press, New York, 1980.

\bibitem{GoHa88}
M.C.~Golumbic and P.L.~Hammer,
\newblock Stability in Circular-Arc-Graphs,
\newblock {\em J. Algorithm}, 9: 314-320, 1988.

\bibitem{Gri83}
J.R.~Griggs,
\newblock Lower Bounds on the Independence Number in Terms of the
Degrees,
\newblock {\em J. Combin. Theory B}, 34: 22-39, 1983.

\bibitem{GrGrGu88}
J.R.~Griggs, M.~Grinstead and D.~Guichard,
\newblock The Maximum Number of Maximal Independent Sets in a
Connected Graph,
\newblock {\em Discrete Mathematics}, 68: 211-220, 1988.

\bibitem{GrPu85}
G.R.~Grimmett and W.R.~Pulleyblank,
\newblock Random Near-Regular Graphs and the Node Packing Problem,
\newblock {\em Operations Research Letters}, 4: 169-174, 1985.

\bibitem{GrLoSc81}
M.~Gr\"{o}tschel, L.~Lov\'{a}sz and A.~Schrijver, 
\newblock The Ellipsoid Method and Its Consequences in Combinatorial
Optimization,
\newblock {\em Combinatorica}, 1: 169-197, 1981.

\bibitem{GrLoSc86}
M.~Gr\"{o}tschel, L.~Lov\'{a}sz and A.~Schrijver, 
\newblock Relaxations of Vertex Packing,
\newblock {\em J. Combin. Theory B}, 40: 330-343, 1986.

\bibitem{GrLoSc88}
M.~Gr\"{o}tschel, L.~Lov\'{a}sz and A.~Schrijver, 
\newblock {\em Geometric Algorithms and Combinatorial Optimization},
\newblock Springer-Verlag (1988).

\bibitem{GrLoSc89}
M.~Gr\"{o}tschel, L.~Lov\'{a}sz and A.~Schrijver, 
\newblock Polynomial Algorithms for Perfect Graphs,
\newblock {\em Annals of Discrete Mathematics}, 21: 325-356, 1989.

\bibitem {GuLeLe82}
U.I.~Gupta, D.T.~Lee and J.Y.T.~Leung,
\newblock Efficient Algorithms for Interval Graphs and Circular-Arc
Graphs,
\newblock {\em Networks}, Vol. 12: 459-467, 1982.

\bibitem{GuSh84}
Y.~Gurevich and S.~Shelah,
\newblock Expected Computation Time for Hamiltonian Path Problem and
Clique Problem,
\newblock {\em Technical Report}, Computing Research Laboratory, The
Univ. of Michigan, 1984.

\bibitem{HaPaRoSa87}
W.W.~Hager, P.M.~Pardalos, I.M.~Roussos and H.D.~Sahinoglou,
\newblock Active Constraints, Indefinite Quadratic Programming and
Test Problems, 
\newblock {\em Journal of Optimization Theory and Applications},
Vol. 68, No. 3: 499-511, 1991.

\bibitem{HaFr69}
S.L.~Hakimi and H.~Frank,
\newblock Maximum Internally Stable Sets of a Graph,
\newblock {\em J. of Math. Anal. and Appl.}, 25: 296-308, 1969.

\bibitem{HaHaSi80}
P.L.~Hammer, P.~Hansen and B.~Simeone,
\newblock Vertices Belonging to All or to no Maximum Stable Sets of
a Graph,
\newblock {\em FUCAM Research Report}, 1980.

\bibitem{Han75}
P.~Hansen,
\newblock Degres et Nombre de Stabilite d'un Graph,
\newblock {\em Cahiers du CERP}, 17: 213-220, 1975.

\bibitem{Han79}
P.~Hansen,
\newblock Upper Bounds for the Stability Number of a Graph,
\newblock {\em Revue Roumaine de Math. Pures et Appliquees}, 24:
1195-1199, 1979.

\bibitem{Han80}
P.~Hansen,
\newblock Bornes et Algorithmes Pour les Stable d'un Graphe,
\newblock In {\em Regards sur la Theory des Graph} (eds. P.~Hansen
and D.~de~Werra), Presses Polytechniques Romandes, 1980.

\bibitem{HaMl92}
P.~Hansen and N.~Mladenovic,
\newblock Two Algorithms for Maximum Cliques in Dense Graphs,
\newblock {\em Technical Report}, Ecole des Hautes Etudes
Commerciales, Montreal, Canada, 1992.

\bibitem{HaRo57}
F.~Harary and I.C.~Ross,
\newblock A Procedure for Clique Detection Using the Group Matrix,
\newblock {\em Sociometry}, 20: 205-215, 1957.

\bibitem{HPV92}
J.~Hasselberg, P.M.~Pardalos and G.~Vairaktarakis,
\newblock Test Case Generators and Computational Results for the
Maximum Clique Problem,
\newblock {\em Working Paper, University of Florida}, 1992.

\bibitem{Hay85}
R.B.~Hayward,
\newblock Weakly Triangulated Graphs,
\newblock {\em J. of Combin. Theory B}, 39: 200-209, 1985.

\bibitem{HaHoMa90}
R.~Hayward, C.T.~Hoang and F.~Maffray,
\newblock Optimizing Weakly Triangulated Graphs,
\newblock {\em Graphs and Combinatorics}, 5: 339-349, 1989. See also
{\em Erratum}, Vol. 6: 33-35, 1990.

\bibitem{Hed85}
B.~Hedman,
\newblock The Maximum Number of Cliques in Dense Graphs,
\newblock {\em Discrete Mathematics}, 54: 161-166, 1985.

\bibitem{Hel57}
I.~Heller,
\newblock On Linear Systems with Integral Valued Solutions,
\newblock {\em Pacific J. of Math.}, 7: 1351-1364, 1957.

\bibitem{HoLe88}
C.W.~Ho and R.C.T.~Lee,
\newblock Efficient Parallel Algorithms for Finding Maximal Cliques,
Clique Trees, and Minimum Coloring of Chordal Graphs,
\newblock {\em Inform. Process. Letter}, 28: 301-309, 1988.

\bibitem{Hod88}
C.~Hoded,
\newblock Hard Graphs for the Maximum Clique Problem,
\newblock {\em Discrete Mathematics}, 72: 175-179, 1988.

\bibitem{Hou74}
D.J.~Houck,
\newblock On the Vertex Packing Problem,
\newblock Ph.D. dissertation, The Johns Hopkins University,
Baltimore, 1974.

\bibitem{HoVe77}
D.J.~Houck and R.R.~Vemuganti,
\newblock An Algorithm for the Vertex Packing Problem,
\newblock {\em Operations Research}, 25: 773-787, 1977.

\bibitem{Hsu85}
W.L.~Hsu,
\newblock Maximum Weight Clique Algorithms for Circular-Arc Graphs
and Circle Graphs,
\newblock {\em SIAM J. Comput.}, Vol. 14, No. 1: 224-231, 1985.

\bibitem{Hsu88}
W.L.~Hsu,
\newblock The Coloring and Maximum Independent Set Problems on
Planar Perfect Graphs,
\newblock {\em J. ACM}, Vol. 35, No. 3: 535-563, 1988.

\bibitem{HsIkNe81}
W.~Hsu, Y.~Ikura and G.L.~Nemhauser,
\newblock A Polynomial Algorithm for Maximum Weighted Vertex
Packings on Graphs Without Long Odd Cycles,
\newblock {\em Math. Programming}, 20: 225-232, 1981.

\bibitem{Hub65}
C.H.~Hubbell,
\newblock An Input-Output Approach to Clique Identification,
\newblock {\em Sociometry}, 28: 377-399, 1965.

\bibitem{Jag92}
A.~Jagota,
\newblock Efficiently Approximating Max-Clique in a Hopfield-style
Network,
\newblock {\em Technical Report}, Dept. of Computer Sci., SUNY
Buffalo, 1992.

\bibitem{Joh74}
D.S.~Johnson,
\newblock Approximation Algorithms for Combinatorial Problems,
\newblock {\em J. Computer. and System Sciences}, 9: 256-278, 1974.

\bibitem{Joh75}
L.F.~Johnson,
\newblock Determining Cliques of a Graph,
\newblock {\em Proc. of the fifth Manitoba Conf. on Num. Math.},
429-437, 1975.

\bibitem{JoPa83}
E.L.~Johnson and M.W.~Padberg,
\newblock Degree-two Inequalities, Clique facets, and Bipartite
Graphs,
\newblock {\em Annals of Discrete Mathematics}, 16: 169-188, 1983.

\bibitem{JoYaPa88}
D.S.~Johnson, M.~Yannakakis and C.H.~Papadimitriou,
\newblock On Generating All Maximal Independent Sets,
\newblock {\em Information Processing Letters}, 27: 119-123, 1988.

\bibitem{Joh76}
H.C.~Johnston,
\newblock Cliques of a Graph: Variations on the Bron-Kerbosch
Algorithm,
\newblock {\em Internat. J. Comput. and Inform. Sci.}, 5: 209-238,
1976.

\bibitem {Kan92}	
V.~Kann,
\newblock On the Approximability of the Maximum Common Subgraph
Problem,
\newblock submitted to STACS 1992.

\bibitem {Kar90}
N.~Karmarkar,
\newblock An interior point approach to $NP$-complete problems -
Part I,
\newblock{\em Contemporary Mathematics}, Vol. 114: 297-308, 1990.

\bibitem{KaReRa89}
N.~Karmarkar, M.G.C.~Resende and K.G.~Ramakrishnan,
\newblock An Interior Point Approach to the Maximum Independent Set
Problem in Dense Random Graphs,
\newblock IX Intern. Conf. of the Chilean Comp. Sci. Society and XV
Latin American Conf. on Informatics, Santiago, Chile, 1989.

\bibitem{KaWi85}
R.M.~Karp and A.~Wigderson,
\newblock A Fast Parallel Algorithm for the Maximal Independent Set
Problem,
\newblock {\em J. ACM}, Vol. 32, No. 4, 1985.

\bibitem {KaFu79}
T.~Kashiwabara and T.~Fujisawa,
\newblock $NP$-Completeness of the Problem of Finding a
Minimum-Clique-Number Interval Graph Containing a Given Graph as a
Subgraph,
\newblock {\em Proceedings International Conference on Circuits and
Systems}, 657-660, 1979.

\bibitem{KaMaNaFu92}
T.~Kashiwabara and S.~Masuda, K.~Nakajima and T.~Fujisawa,
\newblock Generation of maximum independent sets of a bipartite
graph and maximum cliques of a circular-arc-graph,
\newblock {\em Journal of Algorithms}, 13: 161-174, 1992.

\bibitem{Kik86}
P.~Kikusts,
\newblock Another Algorithm Determining the Independence Number of a
Graph,
\newblock {\em Elektron. Inf. Verarb. Kybern.} ELK 22: 157-166, 1986.

\bibitem{Kle88}
P.N.~Klein,
\newblock Efficient Parallel Algorithms for Chordal Graphs,
\newblock {\em Proc. 29th Annual Symp. on Foundations of Computer
Science}, IEEE, 150-161, 1988.

\bibitem{KoTh91}
P.G.~Kolaitis and M.N.~Thakur,
\newblock Approximation properties of $NP$ minimization problems,
\newblock {\em Proc. of 6th Annual Conf. on Structures in Computer
Science}, 353-366, 1991.

\bibitem {Kop87}
R.~Kopf,
\newblock Numerical Methods for Determining Independent Sets in
Graphs (in German),
\newblock Ph.D. Thesis, TH Leipzig, 1987.

\bibitem{KoRu87}
R.~Kopf and G.~Ruhe,
\newblock A Computational Study of the Weighted Independent Set
Problem for General Graphs,
\newblock {\em Foundations of Control Engineering}, Vol. 12, No. 4:
167-180, 1987.

\bibitem{Korm79}
S.M.~Korman,
\newblock The graph-colouring problem,
\newblock {\em In "Combinatorial Optimization"} (N. Christofides, P.  
Toth, and C. Sandi, Editors), Jon Wiley \& Sons, New York, 1979,  
211-235.

\bibitem{KuJa85}
M.~Kubal and B.~Jackowski,
\newblock A generalized implicit enumeration algorithm for graph  
coloring,
\newblock {\em Commun. ACM}, Vol. 28, No. 4: 412-418, 1985.

\bibitem{LaSh92}
J.C.~Lagarias and P.W.~Shor,
\newblock Keller's cube-tiling conjecture is false in high
dimensions,
\newblock {\em Manuscript, Bell Laboratories}, 1992.

\bibitem{Law76}
E.L.~Lawler,
\newblock {\em Combinatorial Optimization: Networks and Matroids},
\newblock Holt, Rinehart and Winston, 1976

\bibitem{LaLeKa80}
E.L.~Lawler, J.K.~Lenstra and H.G.R.~Kan,
\newblock Generating all Maximal Independent Sets: $NP$-Hardness and
Polynomial-Time Algorithms,
\newblock {\em SIAM J. Comput.}, 9: 558-565, 1980.

\bibitem {LeMuAb89}
Lecky, Murphy and Absher,
\newblock Graph Theoretic Algorithms for the PLA Folding Problem,
\newblock {\em IEEE Trans on Computer-Aided Design of...}, Vol. 8,
No. 9: 1014-1021, Sept. 1989.

\bibitem{Lei76}
L.J.~Leifman,
\newblock On Construction of All Maximal Complete Subgraphs
(Cliques) of a Graph,
\newblock {Technical Report}, Dept. of Math., Univ. Haifa, Israel,
1976.

\bibitem{Lin86}
N.~Linial,
\newblock Hard enumeration problems in geometry and combinatorics,
\newblock {\em SIAM J. Alg. Disc. Math.}, Vol. 7, No. 2: 331-335,
1986.

\bibitem {LiTa80}
R.~Lipton and R.~Tarjan,
\newblock Applications of a planar separator theorem,
\newblock {\em SIAM J. on Comput.}, Vol. 9, No. 3: 615-626, 1980.

\bibitem {LiTa79}
R.~Lipton and R.~Tarjan,
\newblock A separator theorem for planar graphs,
\newblock {\em SIAM J. Appl. Math.}, 36: 346-358, 1979.

\bibitem{Lou83}
E.~Loukakis,
\newblock A New Backtracking Algorithm for Generating the Family of
Maximal Independent Sets of a Graph,
\newblock {\em Comp. and Maths. with Appls.}, Vol. 9, No. 4:
583-589, 1983.

\bibitem{LoTs81}
E.~Loukakis and C.~Tsouros,
\newblock A Depth First Search Algorithm to Generate the Family of
Maximal Independent Sets of a Graph Lexicographically,
\newblock {\em Computing}, 27: 249-266, 1981.

\bibitem{LoTs82}
E.~Loukakis and C.~Tsouros,
\newblock Determining the Number of Internal Stability of a Graph,
\newblock {\em Intern. J. Comp. Math.}, 11: 207-220, 1982.

\bibitem{LoTs83}
E.~Loukakis and C.~Tsouros,
\newblock An Algorithm for the Maximum Internally Stable Set in a
Weighted Graph,
\newblock {\em Int. J. Comput. Math.}, 13: 117-12, 1983.

\bibitem{Lov79}
L.~Lov\'{a}sz,
\newblock On the Shannon capacity of a graph,
\newblock {\em IEEE Transactions on Information Theory}, 25: 1-7,
1979.

\bibitem{Lov86}
L.~Lov\'{a}sz,
\newblock {\em An Algorithmic Theory of Numbers, Graphs and
Convexity}
\newblock SIAM, Philadelphia, 1986.

\bibitem{Lub86}
M.~Luby,
\newblock A Simple Parallel Algorithm for the Maximum Independent
Set Problem,
\newblock {\em SIAM J. Comput.}, Vol. 15, No. 4: 1036-1053, 1986.

\bibitem{Luc50}
R.D.~Luce,
\newblock Connectivity and Generalized Cliques in Sociometric Group
Structure,
\newblock {\em Psychometrika} 15: 169-190, 1950.

\bibitem{MaSl79}
J.~MacWilliams and N.J.A.~Sloane,
\newblock {\em The Theory of Error Correcting Codes},
\newblock (Elsevier, American ed.), Amsterdam, North-Holland, 1979.

\bibitem{Mag59}
K.~Maghout,
\newblock Sur la Determination des Nombres de Stabilite et du Nombre
Chromatique d'un Graphe,
\newblock {\em C.R. Acad. Sci.}, Paris, 248: 2522-2523, 1959.

\bibitem{Mar64}
P.M.~Marcus,
\newblock Derivation of Maximal Compatibles Using Boolean Algebra,
\newblock {\em IBM J. Res. Develop.}, 8: 537-538, 1964.

\bibitem{MaNa88}
S.~Masuda and K.~Nakajima,
\newblock An Optimal Algorithm for Finding a Maximum Independent Set
of a Circular-Arc Graph,
\newblock {\em SIAM J. Comput.}, Vol. 17, No. 1, 41-52, 1988.

\bibitem{MaNaKaFu90}
S.~Masuda and K.~Nakajima, T.~Kashiwabara and T.~Fujisawa,
\newblock Efficient Algorithms for Finding Maximum Cliques of an
Overlap Graph,
\newblock {\em Networks}, 20: 157-171, 1990.

\bibitem{Mat70}
D.W.~Matula,
\newblock On the Complete Subgraphs of a Random Graph,
\newblock {\em Proc. 2nd Conf. Combin. Theory and Appl.}, Chapel
Hill, NC, 356-369, 1970.

\bibitem{Mat76}
D.W.~Matula,
\newblock The Largest Clique Size in a Random Graph,
\newblock {\em Technical Report CS 7608}, Department of Computer
Science, Southern Methodist University, 1976.

\bibitem{McH90}
J.A.~McHugh,
\newblock {\em Algorithmic graph theory},
\newblock Prentice-Hall, 1990.

\bibitem{MeCu75}
W.~Meeusen and L.~Cuyvers,
\newblock Clique Detection in Directed Graphs: a New Algorithm,
\newblock {\em J. of Comp. and Appl. Math.}, 1: 185-193, 1975.

\bibitem{MeCu79}
W.~Meeusen and L.~Cuyvers,
\newblock An Annotated Bibliography of Clique-Detection Algorithms
and Related Graph-Theoretical Problems,
\newblock {\em CAM Discussion Paper 7909}, State University Center
Antwerp, 1979.

\bibitem{Mey72}
J.C~Meyer,
\newblock Ensembles Stables Maximaux dans les Hypergraphes,
\newblock {\em Comptes Rendus Acad. Sci. Paris}, 274: 144-147,
1972.

\bibitem{Mey76}
H.~Meyniel,
\newblock On the Perfect Graph Conjecture,
\newblock {\em Discrete Mathematics}, 16: 339-342, 1976.

\bibitem{Mey85}
H.~Meyniel,
\newblock A New Property of Imperfect Graphs and Some Consequences,
\newblock {\em Technical Report}, E.R. 1975 CNRS, Paris, 1985.

\bibitem{Miller92}
Webb Miller,
\newblock Building multiple alignments from pairwise alignments,
\newblock {\em To appear in Computer Applications in the  
Biosciences}, 1992.

\bibitem{Min80}
G.J.~Minty,
\newblock On Maximal Independent Sets of Vertices in Claw-free
Graphs,
\newblock {\em J. Combin. Theory B}, 28: 284-304, 1980.

\bibitem{MoMo65}
J.W.~Moon and L.~Moser,
\newblock On Cliques in Graphs,
\newblock {\em Israel Journal of Mathematics}, 3: 23-28, 1965.

\bibitem {Mot91}
R.~Motwani,
\newblock Clique Partitions, Graph Compression and Speeding-up
Algorithms,
\newblock {\em STOC} (Feder-Motwani), 1991.

\bibitem{MoSt65}
T.S.~Motzkin and E.G.~Straus,
\newblock Maxima for Graphs and a New Proof of a Theorem of Turan,
\newblock {\em Canadian Journal of Mathematics}, 17, No. 4: 533-540,
1965.

\bibitem{MuCo72}
G.D.~Mulligan and D.G.~Corneil,
\newblock Corrections to Bierston's Algorithm for Generating Cliques,
\newblock {\em J. Assoc. Comput. Mach.}, 19: 244-247, 1972.

\bibitem{Mur92}
W.J.~Murphy,
\newblock Computing Independet Sets in Graphs with Large Girth,
\newblock {\em Discrete Applied Math.}, Vol. 36, No. 2: 167-170,  
1992.

\bibitem{NaNaSc87}
J.~Naor, M.~Naor and A.A.~Schaffer,
\newblock Fast Parallel Algorithms for Chordal Graphs,
\newblock {\em Proc. 19th Annual ACM Symp. on Theory of Computing},
ACM, 355-364, 1987.

\bibitem{NeSi92}
G.L.~Nemhauser and G.~Sigismondi,
\newblock A strong cutting plane/branch-andbound algorithm for node
packing,
\newblock {\em J. Opl Res. Soc.}, Vol. 43, No. 5: 443-457, 1992.

\bibitem{NeTr74}
G.L.~Nemhauser and L.E.~Trotter,~Jr.,
\newblock Properties of Vertex Packings and Independence System
Polyhedra,
\newblock {\em Math. Programming}, 6: 48-61, 1974.

\bibitem{NeTr75}
G.L.~Nemhauser and L.E.~Trotter,
\newblock Vertex Packings: Structural Properties and Algorithms,
\newblock {\em Math. Programming}, 8: 232-248, 1975.

\bibitem{NeWo88}
G.L.~Nemhauser and L.A.~Wolsey,
\newblock {\em Integer and Combinatorial Optimization},
\newblock Wiley, New York, 1988.

\bibitem{Ola89}
S.~Olariu,
\newblock Weak Bipolarizable Graphs,
\newblock {\em Discrete Mathematics}, 74: 159-171, 1989.

\bibitem{Onn92}
S.~Onn,
\newblock On the combinatorics of permutation polytopes,
\newblock {\em Journal of Combinatorial Theory, Series A}, 1992.

\bibitem{Ost74}
R.E.~Osteen,
\newblock Clique Detection Algorithms Based on Line Addition and
Line Removal,
\newblock {\em SIAM J. Appl. Math.}, 26: 126-135, 1974.

\bibitem{OsTo73}
R.E.~Osteen and J.T.~Tou,
\newblock A Clique-detection Algorithm Based on Neighborhoods in
Graphs,
\newblock {\em Intern. J. Comput. Inf. Sci.}, 2: 257-268, 1973.

\bibitem{Pad73}
M.W.~Padberg,
\newblock On the Facial Structure of Set Packing Polyhedra,
\newblock {\em Mathematical Programming}, 5: 199-216, 1973.

\bibitem{Pad77}
M.W.~Padberg,
\newblock On the Complexity of Set Packing Polyhedra,
\newblock {\em Annals of Discrete Mathematics}, 1: 421-434, 1977.

\bibitem{Pad79}
M.W.~Padberg,
\newblock Covering, Packing and Knapsack Problems,
\newblock {\em Annals of Discrete Mathematics}, 4: 265-287, 1979.

\bibitem{Pad80}
M.W.~Padberg,
\newblock (1,k)-Configurations and Facets for Packing Problems,
\newblock {\em Mathematical Programming}, 18: 94-99, 1980.

\bibitem{PaRa90}
Panconesi and Ranjan,
\newblock Quantifiers and Approximation,
\newblock {\em Proc. STOC 90}, 1990.

\bibitem{PaYa81}
C.~Papadimitriou and M.~Yannakakis,
\newblock The Clique Problem for Planar Graphs,
\newblock {\em Inform. Proc. Letters}, 13: 131-133, 1981.

\bibitem{PaYa88}
C.~Papadimitriou and M.~Yannakakis,
\newblock Optimization, approximation and complexity classes,
\newblock {\em Proc. of the Twentieth Annual ACM STOC}, 229-234,
1988.

\bibitem{PaDe91}
P.M.~Pardalos and N.~Desai,
\newblock An Algorithm for Finding a Maximum Weighted Independent
Set in an Arbitrary Graph,
\newblock {\em Intern. J. Computer Math.} Vol. 38: 163-175, 1991.

\bibitem{PaLi91}
P.M.~Pardalos and Y.~Li,
\newblock Global Quadratic Optimization and the Maximum Clique
Problem,
\newblock {\em Technical Report}, Computer Science Department, The
Penn. State Univ., 1991.

\bibitem{PaPh90}
P.M.~Pardalos and A.T.~Phillips,
\newblock A Global Optimization Approach for Solving the Maximum
Clique Problem,
\newblock {\em Intern. J. Computer Math.}, Vol. 33: 209-216, 1990.

\bibitem{PaRo90.1}
P.~M.~Pardalos and G.~Rodgers,
\newblock Parallel branch and bound algorithms for quadratic
zero-one programming on a hypercube architecture,
\newblock {\em Annals of Operations Research}, Vol. 22: 271-292,  
1990.

\bibitem{PaRo90.2}
P.~M.~Pardalos and G.~Rodgers,
\newblock Computational aspects of a branch and bound algorithm for
quadratic zero-one programming,
\newblock {\em Computing}, Vol. 45: 131-144, 1990.

\bibitem{PaRo92}
P.M.~Pardalos and G.P.~Rodgers,
\newblock A Branch and Bound Algorithm For the Maximum Clique
Problem,
\newblock {\em Computers and Operations Research}, Vol. 19, No. 5:
363-375, 1992.

\bibitem{PaRo87}
P.M.~Pardalos and J.B.~Rosen,
\newblock {\em Constrained Global Optimization: Algorithms and
Applications},
\newblock Springer-verlag, Lecture Notes in Computer Science, Vol.
25, 1987. 


\bibitem{PaUn59}
M.C.~Paull and S.H. Unger,
\newblock Minimizing the Number of States in Incompletely Specified
Sequential Switching Functions,
\newblock {\em IRE TRANS. Electronic Computers}, EC-8: 356-367, 1959. 


\bibitem{Pea70}
E.R.~Peay,~Jr.,
\newblock An Iterative Clique Detection Procedure,
\newblock Michigan Math. Psycol. Program: MMPP 70-4, 1970.

\bibitem{Pea74}
E.R.~Peay,~Jr.,
\newblock Hierachical Clique Structures,
\newblock {\em Sociometry}, 37: 54-65, 1974.

\bibitem{Per40}
O.~Perron,
\newblock Uber Luckenlose Ausfullung des n-dimensionalen Raumes
durch kongruente Wurfel,
\newblock {\em Math. Z.}, 46: 1-26, 161-180. Zbl 22, 202, 1940.

\bibitem{PiQu77}
J.C.~Picard and M.~Queyranne,
\newblock On the Integer-Valued Variables in the Linear Vertex
Packing Problem,
\newblock {\em Math. Prog.}, 12: 97-101, 1977.

\bibitem{Pit82}
B.~Pittel,
\newblock On the Probable Behavior of Some Algorithms for Finding
the Stability Number of a Graph,
\newblock {\em Math. Proc. Cambridge Philos. Soc.}, 92: 511-526,
1982.

\bibitem{PrBa83}
S.~Provan and M.~O.~Ball,
\newblock On the Complexity of Counting Cuts and of Computing the
Probability that a Graph is Connected,
\newblock {\em SIAM J. Comput.}, 12: 777-788, 1983.

\bibitem{Pul79}
W.R.~Pulleyblank,
\newblock Minimum Node Covers and 2-Bicritical Graphs,
\newblock {\em Mathematical Programming}, 17: 91-103, 1979.

\bibitem{Rag88}
P.~Raghavan,
\newblock Probabilistic Construction of Deterministic Algorithms:
Approximating Packing Integer Programs,
\newblock {\em J. Comput. System Sciences}, 37: 130-143, 1988

\bibitem{RaSa88}
J.~Ramanujam and P.~Sadayappanv,
\newblock Optimization by Neural Networks,
\newblock {\em IEEE International Conf. on Nerual Networks}, San
Diego, July 24-27, II: 325-332, 1988.

\bibitem{ReNiDe77}
E.M.~Reigold, J.~Nievergelt and N.~Deo,
\newblock {\em Combinatorial Algorithms: Theory and Practice},
\newblock Prentice-Hall, Englewood Cliffs, NJ, 1977.

\bibitem{Rob86}
J.M.~Robson,
\newblock Algorithms for Maximum Independent Sets,
\newblock {\em J. of Algorithms}, 7: 425-440, 1986.

\bibitem{Ros70}
D.J.~Rose,
\newblock Triangulated Graphs and the Elimination Process,
\newblock {\em J. Math. Anal. Appl.}, 32: 597-609, 1970.

\bibitem{RoTaLe76}
D.J.~Rose, R.E.~Tarjan and G.S.~Leuker,
\newblock Algorithmic Aspects of Vertex Elimination on Graphs,
\newblock {\em SIAM J. Comput.}, 5: 266-283, 1976.

\bibitem{RoUr81}
D.~Rotem and J.~Urrutia,
\newblock Finding Maximum Cliques in Circle Graphs,
\newblock {\em Networks}, 11: 269-278, 1981.

\bibitem {Sag88}
B.E.~Sagan,
\newblock A Note on Independent Sets in Trees,
\newblock {\em SIAM J. Disc. Math.}, Vol. 1, No. 1: 105-108, 1988.

\bibitem {San90}
L.~Sanchis,
\newblock On the Complexity of Test Case Generation for $NP$-hard
Problems,
\newblock {\em Inf. Processing Letters}, 36: 135-140,1990.

\bibitem {San92}
L.~Sanchis,
\newblock Test Case Construction for the Vertex Cover Problem
(extended abstract),
\newblock DIMACS Workshop on Computational Support for Discrete
Mathematics, March 1992.

\bibitem{Sbi80}
N.~Sbihi,
\newblock Algorithme de Recherche d'un Stable de Cardinalit\'{e}
Maximum dans un Graph sans \'{E}toile,
\newblock {\em Discrete Mathem.}, 29: 53-76, 1980.

\bibitem{Sha56}
C.E.~Shannon,
\newblock The Zero-error Capacity of a Noisy Channel,
\newblock {\em I.R.E. Transactions}, 3, 1956.

\bibitem{Sho90}
N.~Z.~Shor,
\newblock Dual Quadratic Estimates in Polynomial and Boolean
Programming,
\newblock {\em Computational Methods in Global Optimization} (P. M.
Pardalos and J. B. Rosen eds.),
\newblock {\em Annals of Operations Research}, Vol. 25: 163-168,  
1990.

\bibitem{Slo89}
N.~J.~A.~Sloane,
\newblock Unsolved Problems in Graph Theory Arising from the Study
of Codes,
\newblock {\em J. Graph Theory Notes of New York}, 18: 11-20, 1989.

\bibitem{Spe71}
J.H.~Spencer,
\newblock On Cliques in Graphs,
\newblock {\em Israel J. Math.}, 9: 419-421, 1971.

\bibitem{Sta79}
W.~Staton,
\newblock Some Ramsey-Type Numbers and the Independence Ratio,
\newblock {\em Trans. Amer. Math. Soc.}, 256: 353-370, 1979.

\bibitem{Ste74}
S.K.~Stein,
\newblock Algebraic tiling,
\newblock {\em Amer. Math. Monthly}, 81: 445-462, 1974.

\bibitem{SwTh81}
M.N.S.~Swamy and K.~Thulasiraman,
\newblock {\em Graphs, Networks, and Algorithms},
\newblock John Wiley and Sons, 1981.

\bibitem{TaChLeHu90}
Y.~Takefuji, L.~Chen, K.~Lee and J.~Huffman,
\newblock Parallel Algorithms for Finding a Near-Maximum Independent
Set of a Circle Graph,
\newblock {\em IEEE Transactions on Neural Networks}, 1: 263-267,
Sept. 1990.

\bibitem{Tar72}
R.~Tarjan,
\newblock Finding a Maximum Clique,
\newblock {\em Technical Report 72-123}, Computer Sci. Dept., Cornell
Univ., Ithaca, NY, 1972.

\bibitem{TaTr77}
R.E.~Tarjan and A.E.~Trojanowski,
\newblock Finding a Maximum Independent Set,
\newblock {\em SIAM Journal on Computing}, 6: 537-546, 1977.

\bibitem{TaYa84}
R.E.~Tarjan and M.~Yannakakis,
\newblock Simple Linear-time Algorithms to Test Chordality of
Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce
Acyclic Hypergraphs,
\newblock {\em SIAM J. Computing}, Vol. 13, No. 3: 566-579, 1984.

\bibitem{Tom85}
I.~Tomescu,
\newblock {\em Problems in Combinatorics and Graph Theory},
\newblock John Wiley and Sons, 1985.

\bibitem{ToKoTa88}
E.~Tomita, Y.~Kohata and H.~Takahashi,
\newblock A Simple Algorithm for Finding a Maximum Clique,
\newblock {\em Technical Report UEC-TR-C5}, 1988.

\bibitem{ToMiTa88}
E.~Tomita, S.~Mitsuma and H.~Takahashi,
\newblock Two Algorithms for Finding a Nera-Maximum Clique,
\newblock {\em Technical Reprot UEC-TR-C1}, 1988.

\bibitem{ToTaTa88}
E.~Tomita, A.~Tanaka and H.~Takahashi,
\newblock The Worst-Case Time Complexity for Finding All the Cliques,
\newblock {\em Technical Report UEC-TR-C5}, 1988.

\bibitem{Tro73}
L.E.~Trotter,
\newblock Solution Characteristics and Algorithms for the Vertex
Packing Problem,
\newblock {\em Technical Report 168}, Dept. of Operations Research,
Cornell University, Ithaca, NY, 1973.

\bibitem{Tro74}
L.E.~Trotter,
\newblock Vertex Packings: Structural Properties and Algorithms,
\newblock {\em Mathematical Programming}, 8: 232-248, 1974.

\bibitem{Tro75}
L.E.~Trotter,
\newblock A Class of Facet Producing Graphs for Vertex Packing
Polyhedra,
\newblock {\em Discrete Mathematics}, 12: 373-388, 1975.

\bibitem{TsIdAvSh77}
S.~Tsukiyama, M.~Ide, H.~Aviyoshi and I.~Shirakawa,
\newblock A New Algorithm for Generating All the Maximum Independent
Sets,
\newblock {\em SIAM J. on Comput.}, Vol. 6, No. 3: 505-517, 1977.

\bibitem{Tur54}
P.~Turan,
\newblock On the Theory of Graphs,
\newblock {\em Colloq. Math.}, 3: 19-30, 1954.

\bibitem{Val79}
L.G.~Valiant,
\newblock The complexity of enumeration and reliability problems,
\newblock {\em SIAM J. Comput.}, 8: 410-421, 1979.

\bibitem{VinArg91}
M.~Vingron and P.~Argos,
\newblock Motif recognition and alignment for many sequences by  
comparison of dot-matrices,
\newblock {\em J. Molecular Biology} 218:33-43, 1991.

\bibitem{VinArg92}
M.~Vingron and P.A.~Pevzner,
\newblock Multiple sequence comparison and n-dimensional image  
reconstruction,
\newblock {\em Working paper}, 1992.

\bibitem{Wei81}
V.K.~Wei,
\newblock Lower Bound on the Stability Number of a Simple Graph,
\newblock Bell Laboratories Technical Memorandum, No. 81-11217-9,
1981.

\bibitem{Wigd83}
A.~Wigderson,
\newblock Improving the performance guarantee for approximate graph 
coloring,
\newblock {\em Journal of the Association for Computing Machinery},
Vol. 30, No. 3: 729-735, 1983.

\bibitem{Wil86.1}
H.S.~Wilf,
\newblock The Number of Maximal Independent Sets in a Tree,
\newblock {\em SIAM J. Alg. Disc. Meth.}, Vol. 7, No. 1: 125-130,
1986.

\bibitem{Wil86.2}
H.S.~Wilf,
\newblock {\em Algorithms and Complexity},
\newblock Prentice-Hall, Englewood Cliffs, New Jersey, 1986.

\bibitem{Wil86.3}
H.S.~Wilf,
\newblock Special Bounds for the Clique and Independence Numbers of
Graphs,
\newblock {\em J. Combin. Theory B}, 40: 113-117, 1986.

\bibitem {WiPiFe87}
S.~Wimer, R.Y.~Pinter and J.~Feldman,
\newblock Optimal Chaining of CMOS Transistors in a Functional Cell,
\newblock {\em IEEE Transactions on Computer-Aided Design of
Integrated Circuits and Systems}, Vol. CAD-6(5): 795-801, Sept. 1987.

\bibitem{Xue91}
J.~Xue,
\newblock Fast Algorithms for Vertex Packing and Related Problems,
\newblock {\em Ph.D Thesis}, GSIA, Carnegie Mellon University, 1991.

\bibitem{Yan88}
M.~Yannakakis,
\newblock Expressing combinatorial optimization problems as linear
programms,
\newblock {\em Proc. of the Twentieth Annual ACM STOC}, 223-228,
1988.

\bibitem{Yan92}
M.~Yannakakis,
\newblock On the approximation of maximum satisfiability,
\newblock {\em Proc. 3rd Annual ACM-SIAM Symp. on Discrete
Algorithms}, 1992.

\bibitem{YuKoLu91}
G.~Yu, P.~Kouvelis and S.~Luo,
\newblock Weighted Vertex Packing Problem for Specially Structured
Geometric Graphs,
\newblock {\em Technical Report}, Dept. of Mgmt. Sci. and Info.
Syst., Univ. of Texas, Austin, 1991.

%

\end{thebibliography}

\end{document}