% $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{.3}


\begin{document}
\title{Minimum Cost Perfect Matching
}
\maketitle
\begin{abstract}
This is pseudocode for Minimum Cost Perfect Matching in Bipartite Graphs
\end{abstract}

\begin{algorithm}
\setcounter{algocf}{2}
\caption{Minimum Cost Perfect Matching in Bipartite Graphs}
\label{algo3}

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

\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{Graph $G$ = ($V$,$E$) with bipartition $U$,$W$ where \text{\textbar}$U$\text{\textbar} = \text{\textbar}$W$\text{\textbar} and costs c.}
\Output{A minimum cost perfect matching $M$ or a deficient set $S$}
\begin{equation}
\vec{y_v}:=\frac{1}{2}min\left\{c_e : e \in E\right\}
\end{equation}
for all $v$ $\in$ $V$ \emph{B}\\
\While{Construct graph $H$ with vertices $V$ and edges
\begin{equation}
\left\{uv\in E : c_uv=\vec{y_u}+\vec{y_v}\right\}
\end{equation}
}
{
\uIf{$H$ has perfect matching $M$}{
\textbf{stop} ($M$ is a minimum cost perfect matching of $G$)
} 
}
Let $S$ $\subseteq$ $U$ be a deficient set for $H$ \emph{B}\\
\uIf{all edges of $G$ with an endpoint in $S$ have an endpoint in $N_H$(S)}
{
	\textbf{stop} ($S$ is a deficient set of G)
}
\begin{equation}
\in:= min\left\{c_{uv}-\vec{y_u}-\vec{y_v}: uv \in E, u \in S, v \notin N_H(S)\right\}
\end{equation}

\begin{equation}
\vec{y_v}:= \left\{
\begin{array}{lr}
    \vec{y_v}+\in \text{ for } v \in S\\
    \vec{y_v}-\in \text{ for } v \in N_H(S) \\
    \vec{y_v}
  \end{array}
\right.
\end{equation}

\end{algorithm}

\end{document}
