% Sample LaTex for CSC 445/545
% I have cut out sections of the writing which
% were not illustrative of important formatting.
%
\documentclass[12pt]{article}
%
% This nextcommand lets you put in .eps files as figures.
%
\usepackage{epsfig}
% This next command gives 1.5 spacing which I would
% like in your submissions so there is room to
% give feedback.
\renewcommand{\baselinestretch}{1.5}
% These mean a common numbering scheme is given for
% theorems, conjectures, corollaries and lemmas.
% The numbering depend on which section they are in.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newcommand{\wbeginproof}{ \noindent {\em Proof. }}
\newcommand{\wendproof}{\bigskip}
\begin{document}
\title{ A Dynamic Programming Approach for Testing Clique Algorithms}
\author{Wendy Myrvold \\ University of Victoria 
\thanks{Supported by NSERC.} 
\and Tania Prsa \\IBM, Toronto  
\and Neil Walker  \\ University of Victoria 
}
\maketitle
\begin{abstract}
Traditionally, practical clique algorithms have been compared 
based on their performance on various random graphs.
We propose a new testing methodology which permits
testing to be completed in a fraction of 
the time required by previous methods. 
\end{abstract}
\section{Introduction}

An {\em undirected graph} $G$
consists of a set $V$ of 
{\em vertices}
and a set $E$ of unordered pairs of vertices 
called {\em edges}.
The number of vertices is called the {\em order}
of the graph, and the number of edges is the {\em size}.
Given a graph $G=(V,E)$,
a {\em clique} in the graph $G$ is a set of pairwise adjacent vertices.
A {\em maximum clique} in $G$ is the largest such set of vertices.
Although the maximum clique problem is NP-complete,
significant progress has been made in developing
effective algorithms.

The class of clique algorithms for which our 
methodology applies are what we call
{\em neighbourhood search algorithms},
and we define these in Section \ref{neigh_search}.
Note how I used a name neigh\_search for the
section number. The number will be correctly
inserted and it means you do not have to worry about
renumering when extra sections are inserted in front.

Here is a figure from another paper just to show
you how to insert them. The figure is Figure \ref{schlegel}.
For correct figure numbering, ensure that the label statement
below goes after the caption statement.

\begin{figure}
\begin{center}
\epsfig{file=Wendy_Myrvold_8dodec.eps}
\caption{A dodecahedron, showing a
maximum independent set (shaded vertices)
and also the two pairs, up to isomorphism, of vertices at distances 4
or more, i.e., ${u, v}$ and ${u, w}$.}
\end{center}
\label{schlegel}
\end{figure}

\section{Neighbourhood Search Algorithms}
\label{neigh_search}

Theorems and lemmas have consecutive labels as defined
in the header since it is very confusing for example to
have a theorem 1 and also a lemma 1. Here are some
examples of Theorem \ref{first_thm} and 
Lemma \ref{second_thm}.

\begin{theorem}
\label{first_thm}
If $G$ is a planar graph on three or more vertices
then the number of edges is at most $3n -6$.
\end{theorem}

\wbeginproof
I made my own commands for starting and ending proofs.
\wendproof

\begin{corollary}
\label{second_thm}
Planar graphs have at most $O(n)$ edges.
\end{corollary}

\wbeginproof
The number of edges is less than $3n$ and this is in $O(n)$.
\wendproof

\begin{lemma}
\label{first_lemma}
Lemmas are usually lesser results than a theorem.
\end{lemma}
\wendproof

The keywords in these references match what I have in the
Wendy\_Myrvold.bib file.
One of the earliest approaches, Algorithm CACM 457 \cite{BK73},
searches all vertices except those
vertices $v$ where $N[v]$ is completely contained
within the neighbourhood of a previously searched vertex.
Balas and Yu \cite{BY86} find a MTIS (Maximally Triangulated Induced
Subgraph) as an aid to determine
a nice colouring of the vertices
in a strategy similar to GREEDY which we describe in the next section.
Balas and Xue \cite{BN93} 
uses bipartite matching algorithms to search for cliques
Finally, two algorithms 
\cite{TT77, Ro85}
are 
of interest because they
provide upper bounds on the time required
to apply this recursive strategy.

\bibliographystyle{plain}
\bibliography{Wendy_Myrvold}
\end{document}