\documentstyle[12pt]{article}
\setlength{\topmargin}{-.5in}
\addtolength{\textheight}{1.5in}
\addtolength{\textwidth}{\evensidemargin}
\addtolength{\textwidth}{\oddsidemargin}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\addtolength{\textwidth}{-1.0\oddsidemargin}
\addtolength{\textwidth}{-1.0\evensidemargin}
\begin{document}
\setlength{\baselineskip}{20pt}

\title{
Solving the Maximum Clique Problem on an MIMD Computer}
\author{
Chung-Kung Yen, Sheng-Lung Peng and Chuan-Yi Tang\\
\\
Institute of Computer Science \\
National Tsing Hua University, HsinChu, Taiwan\\
e-mail: {\tt cytang@cs.nthu.edu.tw}
}
\date{December 31, 1992}

\maketitle

\noindent {}

\section{Motivation}

The class of distributed-memory MIMD computers is the new trend of
supercomputing in the future.  In this project, we solve the maximum
clique problem on Ncube/2 (a new distributed-memory MIMD machine).

\section{Our approaches}

In this section, we present two approaches to solve the maximum clique
problem on Ncube/2.

\begin{enumerate}
  \item[a.] Parallel Branch and Bound Strategy\\
    There have some branch-and-bound based parallel algorithms for
    solving the maximum clique problems[1,2].  Two problems should be
    confidered in designing these algorithms, they are: choosing good
    branching rules and solving the load balancing problem. Sometimes,
    the overhead is huge for efficiently solving these two problems.

  \item[b.] Parallel Enumerating All Combinations\\
    Many combinatorial problems such as the maximum clique, the maximum
    independent set, ..., etc. can be solved straightforwardly by
    enumerating all of the combinations.  As a matter of fact, there have
    some papers that discuss how to enumerate all combinations in parallel
    efficiently[3,4,5]. In our design, we first provide a procedure that
    can generate all combinations based on the ranking and unranking techniques
    discussed in [3,4,5].  Later, we solve the maximum clique problem through
    checking all these generated combinations. The advantages of this approach
    are: load balancing problem is not a problem and the communication cost
    is very low.

\end{enumerate}

\section{Our goal}

The goal of our study is to solve the maximum clique problem by using
parallel branch and bound strategy and parallel enumerating all combinations
approach. We shall implement the two approaches on Ncube/2 and do some
comparsions between them. We believe that the brute-force enumerating method
may work better than branch-and-bound methods for solving most of the NP-hard
graph optimization problems.

\section{References}
\begin{enumerate}
  \item[[1]] P. M. Pardalos and G. P. Rodgers, {\it A Branch and Bound
             Algorithm for The Maximum Clique Problem}, Computers Ops. Res.,
             No. 4, pp. 363-375, 1992.
  \item[[2]] P. M. Pardalos and G. P. Rodgers, {\it Parallel Branch and
             Bound Algorithms for Quadratic Zero-one Programs on A Hypercube
             Architecture}, Ann. Ops. Res., 22 (1990), 271-292.
  \item[[3]] S. G. Akl, {\it The Desgin and Analysis of Parallel Algorithms},
             Prentice-Hall, 1989.
  \item[[4]] B. Y. Wu and C. Y. Tang, {\it Ranking, Unranking and Parallel
             Enumerating Topological Orders}, Proc. of the 1991 International
             Confereence of Parallel Processing, Vol 3, pp. 284-285.
  \item[[5]] B. Y. Wu and C. Y. Tang, {\it The Problem of Lexicographic
             Unranking of Permutation is in NC}, Parallel Computing '91
             Conference, University of London, pp. 384-385.
\end{enumerate}
\end{document}