% $Header: /home/rdv/quantum/genetic-paper/RCS/eaqc-paper.tex,v 1.12 2005/05/29 21:34:00 rdv Exp rdv $
% now how do I set the paper size?
% \documentclass[twocolumn]{article}

\documentclass[onecolumn,doublespace]{article}
\usepackage{times}
\usepackage{graphics}
\usepackage{lscape}
\usepackage{subfigure}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsmath,amsfonts,amssymb}
\usepackage{kbordermatrix,blkarray}
\usepackage[ruled,linesnumbered,vlined]{algorithm2e} 
\pagestyle{plain}

\bibliographystyle{unsrt}   %>>>> makes bibtex use spiebib.bst

% \input{psfig}
\input{epsf}
% \epsfverbosetrue

%\def\comment#1{$\Rightarrow${\small\em #1}}
\def\comment#1{}
\newenvironment{chapterquote}
  {\begin{quotation}
      \sf}
  {\end{quotation}}
\def\cq#1#2{\begin{chapterquote}#1\flushright\textbf{#2}\end{chapterquote}}


\newcommand{\icol}[1]{% inline column vector
  \left(\begin{smallmatrix}#1\end{smallmatrix}\right)%
}

\newcommand{\irow}[1]{% inline row vector
  \begin{smallmatrix}(#1)\end{smallmatrix}%
}

\SetAlgoCaptionSeparator{.4}


\begin{document}
\title{Perfect Matching
}
\maketitle
\begin{abstract}
  This is pseudocode for Perfect Matching in Bipartite Graphs, adapted
  from the paperback edition of \emph{A Gentle Introduction to
    Optimization}, B. Guerin \emph{et al.}  This is used as a
  subroutine to find any perfect matching on a subgraph of the larger
  bipartite graph in the Hungarian Algorithm, whose goal is to find a
  minimum weight perfect matching.

The operator $\Delta$ is essentially an exclusive OR (XOR) of the two
sets:
\begin{align}
M \Delta P = (M\cup P) \setminus (M\cap P).
\end{align}
Executed on an alternating paths of links included in versus excluded
from the set and a second path including at leaast part of that first
set, it has the behavior of flipping the ones included versus
excluded.

I believe this algorithm as stated assumes that the input graph $H$ is
connected.
\end{abstract}

\begin{algorithm}
\setcounter{algocf}{2}
\caption{Perfect Matching}
\label{algo3}

\AlgoDisplayBlockMarkers\AlgoDisplayGroupMarkers\SetAlgoBlockMarkers{ \{}{ \}\ }%
\SetAlgoNoEnd\SetAlgoNoLine

\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{Bipartite graph $H = (V,E)$ with bipartition $U$,$W$ where $ |U| = |W| \geq 1$}
\Output{A perfect matching $M$, or a deficient set $B$ $\subseteq$ $U$.}
$M := \varnothing$ \\
$T := (\{r\},\varnothing$) where $r \in U$ is any $M$-exposed vertex \\
\While{(1)}
{
	\uIf{$\exists$  $uv$ where $u$ $\in$ $B(T)$ and $v \notin V(T)$ }
	{
		\uIf{$v$ is $M$-exposed} 
		{
			$P := T_{ru} \cup \{uv\}$\\
			$M := M\Delta P$ \\
			\lIf{$M$ is a perfect matching}{\textbf{stop}}
			$T := (\{r\},\varnothing)$ where $r \in \cup$ is any $M$-exposed vertex.
		}\Else{
			Let $w \in V$ where $vw \in M$ \\
			$T := (V(T) \cup \{v,w\}, E(T) \cup \{uv,vw\})$
		}
	}\Else {
		\textbf{stop} $B(T) \subseteq U$ is a deficient set
	}
}

\end{algorithm}

\end{document}
