\documentstyle{article}

\begin{document}
\title{Improved Implementations of Dynamic Sequential Coloring Algorithms}
\author{Craig Morgenstern \\
	Department of Computer Science \\
	Texas Christian University \\
	Fort Worth, Texas 76129 \\ \\
	{\bf Tech Report: CoSc-91-1}
	}
\date{27 April 1991}
\maketitle
\thispagestyle{empty}

\begin{abstract}
Let $G=(V,E)$ be a simple undirected graph with $n$ vertices and $m$ 
edges.  We describe improvements to several sequential
algorithms for coloring $G$ with $k$ colors, including
a $\Theta (m)$ implementation of Br\'{e}laz's
saturation algorithm which improves the previous best 
$O(m \log n)$ implementation, and a $O(km)$ implementation
of Leighton's RLF independent set selection algorithm improving the
old $O(km + n^2)$ implementation.  Our implementations use 
a new priority queue structure and the run times are computed with
simple amortized arguments.
\end{abstract}

\addtolength{\baselineskip}{12pt}   %double space

\section{Introduction}
A (proper) $k$--coloring of $G$ is a mapping 
$C: V(G) \rightarrow  \{1, \ldots, k\}$ 
so that no two vertices joined by an edge are assigned the same color.  The
graph coloring optimization problem is to prescribe a coloration to 
$G$ while minimizing $k$.
Specifing an optimal coloration for an arbitrary graph is a well known
{\bf NP}--hard problem and so it is believed that no polynomial time
algorithm can guarantee an optimal coloring on all graphs.  

In this paper, we focus on polynomial time coloring algorithms 
that proceed by 
adding vertices in a sequential manner to the portion of the graph already 
colored.
Each newly adjoined vertex is assigned some color not already allocated
to one of its colored neighbors, and a vertex, once colored, cannot be 
recolored later. Algorithms of this
type are simple to implement and usually run in time proportional to a low
degree polynomial in the number of edges of the graph.  Sequential algorithms 
belong to the meta-algorithm given in Figure~\ref{fig:Seq}. 

Various heuristics for choosing $\sigma$ and for selecting an available color 
give rise to specific algorithms. We say that a sequential coloring algorithm is
static if $\sigma$ is completely determined before any colors are assigned. 
Static algorithms attempt to exploit a knowledge of the structure of the
graph that can be obtained from a (polynomial time) preprocessing stage.  A
sequential coloring algorithm is said to be dynamic if the determination 
of $\sigma$ is interleaved with the color assignment steps; that is, if the
choice of $\sigma(i)$ depends on the color assignments to the colored
vertices $\sigma(1), \ldots , \sigma(i-1)$.  

\subsection{Notation}
The vertex and edge sets of G are denoted by $V(G)$ (or just $V$)
and $E(G)$ (or just $E$), $n$ denotes the number of vertices and
$m$ denotes the number of edges.
We will let $U_i$ denote the set of all uncolored vertices 
at step $i$ of the algorithm of Figure~\ref{fig:Seq}, and we let
$\overline{U}_i$ denote the set of all colored vertices at step $i$.
If $H \subseteq V(G)$, then $\left < H \right >$ denotes the subgraph of $G$
induced by the members of $H$.  We let $deg_H(v)$ denote the number of
vertices of $H$ that are adjacent to~$v$ in $\left < H \right >$ and 
we let $N_H(v)$ denote the set containing both $v$ and 
all vertices adjacent to~$v$ in $\left< H \right>$.
We shall sometimes write $H$ when we really mean $\left < H \right >$; 
the exact meaning will be clear from context.

\subsection{Color Assignment Methods}
Sequential coloring algorithms typically assign colors in one of two ways.  
At step $i$, we say that a color is feasible for $\sigma(i)$ if it has not
already been assigned to a vertex in $N_{\overline{U}_{i-1}} (\sigma(i))$
(otherwise, the color is said to be infeasible for $\sigma(i)$).  The simple
greedy color assignment method assigns to $\sigma(i)$ the minimal feasible 
color label.  This method will require only $O(m)$ time overall since
every vertex, $v$, will be
assigned some color label from the set $\{\,1, \ldots , deg_G(v)+1 \,\}$. Hence,
the work done to assign all colors takes time proportional to
\[
\sum_{v=1}^{n} deg_G(v) = 2m .
\]
The best-available method proceeds by choosing a color from the set of
feasible colors for $\sigma(i)$ that is infeasible for the largest number of 
vertices in $N_{\overline{U}_{i-1}} (\sigma(i))$. That is,
we choose a feasible color such that the number of uncolored neighbors for
which the color is already infeasible is maximized.  This heuristic seeks to
avoid assigning $\sigma(i)$ a color that will unnecessarily cause the
introduction of a new color to a neighbor---it requires time proportional to 
$km$ to assign all colors, where $k$ is the total number of colors used.  
The analysis of algorithms presented in this paper 
is done with respect to the greedy color assignment method.
 
\subsection{Overview}
The best performing dynamic sequential algorithms include 
the {\em saturation\/} 
algorithm, first proposed by Br\'{e}laz~\cite{BRE1979}, and the {\em RLF
independent set selection\/} algorithm proposed by Leighton~\cite{LEI1979}.
Several studies~\cite{JOH1990,KUB1985,LEI1979,MOR1991,MOR1990,TUR1988}
have shown that these two algorithms yield superior 
performance over the other known sequential algorithms on a wide variety
of graphs.  These studies also illustrate how the algorithms can be used 
to an advantage as a component in more elaborate coloring algorithms.

Br\'{e}laz initially claimed a $O(n^2)$ run time for his saturation heuristic, 
and this was improved by Turner~\cite{TUR1988}
with a $O(m \log n)$ implementation---
we give a further improvement in this paper with a detailed description of a 
new $\Theta(m)$ implementation.  
In~\cite{LEI1979}, Leighton describes an $O(km + n^2)$ implementation of his
RLF independent set selection algorithm, which we improve with an $O(km)$
implementation.  Both improvements are obtained by using a new special purpose
priority queue that we call a {\em saturation heap}.

The rest of this paper is organized as follows: 
\begin{itemize}
\item In Section~2, we describe the saturation algorithm, the
necessary operations needed to support it, and two new, very simple,
$O(m \log n)$ implementations.
\item Section~3 contains our $\Theta(m)$ implementation of saturation 
and a description of the saturation heap structure it uses.  An enhancement 
to the saturation heuristic is also described.
\item Section~4 contains our $O(km)$ implementation of Leighton's RLF
algorithm using the saturation heap of Section~3.
\end{itemize}
 
\section{The Saturation Heuristic}
Saturation differs from the static sequential algorithms in that 
$\sigma$ is not fixed before the coloring stage begins; if $i-1$ vertices have
been colored, then the choice of $\sigma(i)$
depends on the color assignments to $\sigma(1), \ldots , \sigma(i-1)$.  
Hence, saturation orders the vertices in a dynamic fashion that depends on
the current partial coloration of the graph at every step.  At step
$i$, after $i-1$ vertices have been colored, define $F_i(v)$ for any 
$v \in U_i$ to be the set of colors forbidden to $v$;
\[
F_i(v) = \left\{ c(w) \, : \, w \in N_{\overline{U}_{i-1}}(v) \right\}.
\]
Then the {\em saturation degree\/} of uncolored vertex $v$ at step $i$ is
defined to be
\[
d_i(v) = \left| F_i(v) \right|
\]
and the {\em saturation weight\/} of uncolored vertex $v$ at step $i$ is given
by
\[
D_i(v) = n d_i(v) + deg_{U_i}(v) .
\]
Note that $D_i$ defines an ordering on the vertices of $U_i$ with the
saturation degree being the primary ordering and the uncolored vertex degree
in $U_i$ being the secondary ordering.  The saturation heuristic proceeds by
choosing a vertex from $U_i$ with maximal saturation weight to color next.  
The motivation behind the primary ordering is that uncolored vertices 
with the most highly constrained set of feasible colors should be colored
first to avoid the creation of a new color class when possible.
The secondary ordering is used to break ties and
has the same motivation as the largest-first heuristic \cite{DUN1976}.

To implement the saturation heuristic, we need a priority queue of
vertex labels with primary and secondary keys to support the selection of a
vertex with maximal saturation weight.   We want the following operations:
\begin{list}{}
   {\setlength{\labelwidth}{1.75in}
    \setlength{\leftmargin}{1.75in}
    \setlength{\rightmargin}{0in}
    \setlength{\labelsep}{0in}
   }
\item[{\em create\_heap\/$(h)$}\hfill] 
--- A procedure that initializes heap $h$ to be empty.
\item[{\em empty\_heap\/$(h)$}\hfill] 
--- A boolean valued function that returns true if the heap structure is empty 
and false otherwise.
\item[{\em heap\_insert\/$(h, v, d_1, d_2)$}\hfill]
--- A procedure to insert vertex 
$v$ into heap $h$ where $v$ has primary key $d_1$ and secondary key~$d_2$.
\item[{\em heap\_delete$(h, v)$}\hfill]
--- A procedure to remove vertex $v$ from heap~$h$.
\item[{\em heap\_sift\/$(h, v, \delta_1, \delta_2)$}\hfill]
--- A procedure that adds $\delta_1$ to the primary key of $v$ in
heap $h$, adds $\delta_2$ to the secondary key, and sifts $v$ to
its new proper position in~$h$.
\item[{\em heap\_delete\_max\_max\/$(h)$}\hfill]
--- A function that returns the vertex with maximal secondary 
key amongst those vertices with maximal
primary key in heap $h$, and removes that vertex from~$h$.
\end{list}

Once a vertex, $v$, of maximal saturation weight has been selected to be
colored next, we must find the minimal feasible color available for assignment
to $v$.  Additionally, we must then update the key values used to compute the
saturation weights of $v$'s uncolored neighbors.  Thus, unlike static
sequential algorithms, we not only need to find the minimal 
feasible color for a vertex, but we also need to be able to determine if a
particular color has been used on the colored neighborhood of a vertex
(to update the saturation weight of the vertex).  A data type for
these tasks, called an {\em available color set}, need only include the
following operations:
\begin{list}{}
   {\setlength{\labelwidth}{1.75in}
    \setlength{\leftmargin}{1.75in}
    \setlength{\rightmargin}{0in}
    \setlength{\labelsep}{0in}
   }
\item[{\em create\_avail\/$(v, n)$}\hfill]
--- A procedure that initializes the set so that $n$ color labels, $1, \ldots ,n$
are available for assignment to vertex $v$.
\item[{\em delete\_avail\/$(v, c)$}\hfill]
--- A procedure that makes color label $c$ unavailable for assignment to vertex $v$.
\item[{\em min\_avail\/$(v)$}\hfill]
--- A function that returns the smallest color label still available 
for assignment to vertex $v$.
\item[{\em is\_avail\/$(v, c)$}\hfill]
--- A boolean-valued function that returns true if color label $c$
is still available for assignment to vertex $v$.
\end{list}

\subsection{Previous Implementations}
Figure~\ref{fig:SAT} gives a high-level implementation of the saturation 
algorithm in terms of our priority queue and available color set data types.  
Br\'{e}laz~\cite{BRE1979} envisioned a standard heap for the priority queue 
and a bit vector to implement the available color sets. Using a
standard heap, the time taken by the coloring loop of Figure~\ref{fig:SAT}
is $O(m \log n)$ since the number of sift operations performed is proportional 
to $m$, and each sift can take time proportional to $\log n$.  
But Br\'{e}laz initializes the color sets to make all $n$ possible color 
labels available for each of the $n$ vertices.  This initialization dominates, 
and so the running time of his implementation is seen to belong to 
$\Theta(n^2)$. Thus the obstacle to an overall $O(m \log n)$ run time is the
initialization of the bit vectors.  

Turner~\cite{TUR1988} obtains an $O(m \log n)$ implementation
of saturation by using his ``shrinking set'' data structure to
support the needed available color set operations, along with a standard heap
structure to support the needed priority queue operations. 
The shrinking set allows the {\em create\_avail\/} operation to be done in 
constant time and all other available color set operations to be performed 
in $O(\log k)$ time. But the shrinking set is somewhat involved
in that it must use a balanced binary search tree---we shall give simpler 
ways to implement the available color set operations so that 
a $O(m \log n)$ saturation implementation still results.  

Both Br\'{e}laz~\cite{BRE1979} and Turner~\cite{TUR1988} initialize all of 
the $n$ available color sets to contain all $n$ color labels instead of just 
the first $1+deg_G(v)$ color labels---presumably because of the 
{\em is\_avail\/} test performed when updating the saturation weight
of the uncolored neighbors of a vertex just colored.  The strict definition of 
saturation degree does not allow us to disregard a color label assigned 
to a neighbor of an uncolored vertex, $v$, when the color label is larger 
than $1+deg_G(v)$ (even though this color assignment does not impede $v$'s 
ability to be colored). 

\subsection{Two Simple $O(m \log n)$ Implementations}
Our first $O(m \log n)$ implementation of the saturation heuristic
is motivated by the fact that the greedy color selection will always assign each
vertex, $v$, a color chosen from the set of colors 
$\{1, \ldots, deg_G(v) + 1\}$.  We can achieve a $O(m)$ total time bound on 
the sequence of available color set operations (using the bit vector scheme) 
if we modify the definition of saturation degree to be 
\[
d_i(v) = \left| F_i(v) \cap \{1, \ldots, deg_G(v) + 1\} \right|.
\]
This new definition makes more sense than the original since the assignment 
of any color, $c$, $k \geq c > deg_G(v)$, to any neighbor of the uncolored 
vertex $v$ will not impede our ability to later assign $v$ one of the 
$k$ colors currently in use.  It requires that we modify lines (**) and (***) 
of Figure~\ref{fig:SAT} as follows (where CAND is the ``conditional and'' 
operation):
\begin{list}{}
   {\setlength{\labelwidth}{1.0in}
    \setlength{\leftmargin}{1.0in}
    \setlength{\rightmargin}{0in}
    \setlength{\labelsep}{0in}
   }
\item[(**)\hfill] create\_avail$(v, deg_G(v) +1)$;
\item[(***)\hfill] if $(c \leq deg_G(w) +1)$ CAND is\_avail$(w,c)$ then $\ldots$
\end{list}
Thus, using bit vectors for the available color sets and a standard heap, we
have a $O(m \log n)$ implementation---
the $n$ calls to {\em create\_avail} and {\em min\_avail} will
require $O(m)$ total time and the $O(m)$ calls to {\em is\_avail} and 
{\em delete\_avail} will also require $O(m)$ total time.

Our second $O(m \log n)$ implementation of the saturation heuristic uses
the original strict definition of saturation degree together with a well known 
technique to determine if a cell of an array has been previously 
accessed or not, eliminating the need to explicitly initialize all cells 
before any accesses are made.  In Figure~\ref{fig:LZ}, a data structure 
called a {\em lazy array\/} is presented that supports the following 
three constant time operations:
\begin{list}{}
   {\setlength{\labelwidth}{1.75in}
    \setlength{\leftmargin}{1.75in}
    \setlength{\rightmargin}{0in}
    \setlength{\labelsep}{0in}
   }
\item[{\em create\_lazy\_array\/$(L)$}\hfill]	
--- A procedure to initialize the lazy array $L$ to be empty.
\item[{\em touched\/$(L, a)$}\hfill]
--- A boolean-valued function that returns true when
address $a$ of lazy array $L$ has previously been accessed, 
and false otherwise.
\item[{\em touch\/$(L, a)	$}\hfill]
--- A procedure that accesses (touches) address $a$ of lazy array $L$.
\end{list}
To be able to determine if a cell of an arbitrary array $A$ has been accessed, 
a lazy array should be maintained that is parallel to $A$.  

A simple and efficient implementation of the $n$ available color sets using 
$n$ lazy arrays is given in Figure~\ref{fig:LZsets}.  The operations 
{\em create\_avail}, {\em delete\_avail\/} and {\em is\_avail\/} are all 
seen to need only constant time, while the operation {\em min\_avail\/} is 
seen to require time proportional to $deg_G(v)+1$ by the pigeonhole principle.
Since there are at most $m$ calls to {\em delete\_avail\/} and 
{\em is\_avail}, and at most $n$ calls to {\em create\_avail\/} and 
{\em min\_avail}, the total time taken by the avail set operations in the 
saturation algorithm is $O(m)$.  Hence, this available color 
set data structure together with a standard heap also gives an 
$O(m \log n)$ implementation of saturation; the obstacles to an overall 
$O(m)$ implementation are the $O(m)$ {\em heap\_sift\/} operations and 
the $O(n)$ {\em heap\_delete\_max\/} operations.  In the next section, 
we remove these obstacles.

\section{A Linear Time Implementation of the Saturation Heuristic}
The basis for a $\Theta(m)$ implementation of saturation is a new priority
queue, called a {\em saturation heap}, that
uses lazy arrays to avoid the need for explicit initialization and also 
takes full advantage of the simplifying constraints imposed on the heap 
by the saturation algorithm. A generic heap is too powerful since we know 
that the heap need only contain a maximum of $n$ vertices with 
labels $1, \ldots, n$, and that any
primary or secondary key, $d$, is an integer in the range $0 \leq d < n$.  
Additionally, we know that the primary key (the saturation degree) is~0 when the
vertices are first inserted into the heap, and that every sift operation is 
passed a primary key change value, $\delta_1$, of either 0 or 1 and a 
secondary key change value, $\delta_2$, of $-1$.

The saturation heap requires that we support lists of vertices under the 
constraint that no vertex may appear on more than one list at the same 
time; we will need to perform the operations listed below:
\begin{list}{}
   {\setlength{\labelwidth}{1.75in}
    \setlength{\leftmargin}{1.75in}
    \setlength{\rightmargin}{0in}
    \setlength{\labelsep}{0in}
   }
\item[{\em create\_vlist\/}$(L)$\hfill]
--- Initialize list $L$ to be empty.  
\item[{\em vlist\_insert\/}$(L,v)$\hfill]
--- Insert vertex $v$ onto list $L$.
\item[{\em vlist\_delete\/}$(L,v)$\hfill]
--- Delete vertex $v$ from list $L$.
\item[{\em empty\_vlist\/}$(L)$\hfill]
--- Returns true if $L$ is empty and false otherwise.
\item[{\em vlist\_select\/}$(L)$\hfill]
--- Returns the label of an arbitrary vertex on $L$.
\end{list}
Figure~\ref{fig:vlist} gives an implementation of these vertex lists using 
doubly linked lists of nodes that are directly addressable by vertex label.  

By way of motivation, we first describe a weak saturation heap structure for 
a version of saturation that we call {\em weak saturation}, in which we 
ignore the value of the secondary keys and always choose a vertex to color 
next of maximal saturation degree instead of maximal saturation weight.  We
show that weak saturation can be implemented to run in $\Theta(m)$ time, then 
we expand the weak saturation heap to account for secondary keys and prove 
the same result for the full saturation algorithm.  

\subsection{Weak Saturation}
We give an implementation of the weak saturation heap in 
Figure~\ref{fig:wsatheap}; it ignores secondary key values and consists of an 
array of ``buckets,'' each containing vertices with identical primary keys.
An invariant for the weak saturation heap is that {\it maxprimary} is at 
least as large as the largest primary key of any vertex in the heap and that 
{\it minprimary} is no larger than the smallest primary key of any vertex 
in the heap.

The complexity of the weak saturation heap operations is analyzed using a very 
simple potential function to carry out an amortized argument.  Our potential 
function is a mapping from the set of all possible (weak) saturation heap 
configurations into $\{0, \ldots, n\}$.  For any sequence of weak saturation 
heap operations, the amortized time, $a_i$, of the $i$-th operation is given by
\[
a_i = t_i + \Phi_i - \Phi_{i-1},
\]
where $t_i$ is the actual time taken to perform the operation, $\Phi_i$ is the 
potential value after the $i$-th operation, and $\Phi_{i-1}$ is the potential 
before the operation.  To obtain an upper bound on the time taken by a 
sequence of these heap operations, we sum over the amortized times of all 
the operations in the sequence.

\newtheorem{thm31}{Theorem}[section]
\begin{thm31}
\label{weakthm}
The implementation of the weak saturation algorithm using the heap given in
Figure~\ref{fig:wsatheap} runs in $\Theta(m)$ time.
\end{thm31}

\noindent
{\bf Proof}\ \ 
We define $\Phi_i$ to be the value of the weak saturation heap variable 
{\em maxprimary\/} after the $i$-th operation, where $\Phi_0 = 0$.  The 
sequence of operations that is performed on the heap is implicitly described in 
Figure~\ref{fig:SAT}. We see that for every sift operation, 
$0 \leq \delta_1 \leq 1$, and that for every insert operation, $d_1 = 0$.  
We claim that all operations in this sequence need only constant amortized 
time except for {\em create\_heap}, which requires $\Theta(n)$ amortized time.
This is easy to see for {\em create\_heap\/} and {\em empty\_heap\/} since
they do not alter the value of {\em maxprimary\/} and so their amortized times 
are equal to their actual times.  The {\em heap\_insert\/} operation appears 
in the sequence with $d_1 = 0$, so its amortized time is also identical to 
its actual time which is constant. Since we have $0 \leq \delta_1 \leq 1$ for 
every sift operation, we see that if the $i$-th operation of the sequence 
is a {\em heap\_sift}, then the amortized time is at most two.  Finally,
if the $i$-th operation of the sequence is a {\em heap\_delete\_max\_max},
then the actual time, $t_i$, is seen to be proportional to
$1 + \Phi_{i-1} - \Phi_i$, and so the amortized time is constant since 
$a_i = \left( 1 + \Phi_{i-1} - \Phi_i \right) + \Phi_i - \Phi_{i-1}$.
Summing over a sequence of $s$ weak saturation heap operations used by the 
saturation algorithm, we have
\[
\sum_{i=1}^{s} t_i = \sum_{i=1}^{s} a_i + \Phi_{i-1} - \Phi_i 
= \Phi_0 - \Phi_s + \sum_{i=1}^{s} a_i \leq \sum_{i=1}^{s} a_i
\]
since $\Phi_0 = 0$ and $\Phi_s >= 0$ when the algorithm terminates.  But we 
see that $\sum_{i=1}^{s} a_i \in O(m)$ since we have a single call 
to {\em create\_heap\/} that requires $O(n)$ amortized time, $n$ calls 
to {\em heap\_insert\/} with a primary value of 0 requiring $O(n)$ total 
amortized time, $O(m)$ calls to {\em heap\_sift\/} requiring $O(m)$ amortized 
time, and $n$ calls to {\em heap\_delete\_max\_max\/} requiring $O(n)$ total 
amortized time.  Finally, as noted earlier, the available color sets can be 
implemented to use only $O(m)$ total time, and since we have to touch each 
edge at least once to color the graph, we have our result that
weak saturation can be implemented to run in time $\Theta(m)$. 
\hfill $\Box$
\medskip
 
\subsection{Full Saturation}
To implement the full saturation algorithm, we must somehow partition 
each vertex list corresponding to a particular saturation degree into 
parts, each corresponding to vertices of the same uncolored degree.  
This must be done in such a way as to maintain the $O(m)$ total time 
obtained for the weak saturation algorithm.  A close inspection of the
weak saturation heap reveals that the only operation in which there is 
some ``slack'' to work with a secondary order partitioning of vertices 
with the same primary order is {\em heap\_delete\_max\_max}.  
Both {\em create\_heap\/} and {\em heap\_insert\/} are done at initialization, 
and {\em heap\_sift\/} is done as many as $m$ times, which 
requires that the sift operation remain a constant time operation.  However, 
{\em heap\_delete\_max\_max\/} is done only $n$ times and it was shown to use 
only constant amortized time in the weak saturation heap.  This implies
that our only hope is to use a direct access structure to implement the 
partition, since we can afford to do some searching during a 
{\em heap\_delete\_max\_max}, but cannot afford a search when updating the 
keys with the {\em heap\_sift\/} operations.  A large direct access structure 
is feasible since explicit initialization can be avoided using our 
lazy array scheme.

Hence, instead of maintaining a vertex list associated with each primary 
key value, we associate with each primary key an array indexed by secondary 
key values of vertex lists containing vertices with the particular primary 
and secondary keys.  This scheme allows us to access the required vertex list 
directly when updating the saturation weight of a vertex via a sift operation. 
All that remains is somehow to bound the time needed to find a vertex of 
maximal saturation weight during a {\em heap\_delete\_max\_max\/} operation.  
But the vertex with maximal saturation weight has a secondary key value that is
bounded by its overall vertex degree; so if we know the maximal primary key 
and the number of nonempty vertex lists in the associated vertex list array, 
then we can be assured that the time to search the array for a vertex of 
maximal secondary key value will be bounded by the secondary key value itself. 
Since the sum of the vertex degrees is twice the 
number of edges, the runtime of the whole scheme is proportional to $m$.  
Figure~\ref{fig:satheap} describes the new saturation heap in detail, and 
Theorem~\ref{strongthm} makes the previous discussion precise; this is 
essentially the scheme first reported by Morgenstern~\cite{MOR1988}.

\newtheorem{thm32}[thm31]{Theorem}
\begin{thm32}
\label{strongthm}
The full saturation algorithm runs in $\Theta(m)$ time when implemented
using the saturation heap given in Figure~\ref{fig:satheap}.
\end{thm32}

\noindent
{\bf Proof}\ \
The proof is nearly identical to that of Theorem~\ref{weakthm}; let $\Phi_i$
be the value of the heap variable {\em maxprimary}, and note that 
{\em create\_heap\/} has actual and amortized time of
$O(n)$ while {\em empty\_heap\/} and {\em heap\_delete\/} both have constant 
actual and amortized times.  The sequence of heap operations defined by the 
saturation algorithm constrains 
all {\em heap\_insert} operations to be passed a primary key of 0, and so all 
{\em heap\_insert\/} operations take constant actual and amortized time.  
Likewise, all {\em heap\_sift\/} operations are constrained to have 
$\delta_1$ either 0 or 1, and so their actual and amortized 
times are constant.  The only change from Theorem~\ref{weakthm} involves the 
{\em heap\_delete\_max\_max\/} operation.  While the actual time to perform a 
{\em heap\_delete\_max\_max\/} can be as bad as $O(n)$, we see that the 
amortized time is identical to the value of the secondary key (the uncolored 
degree) of the vertex returned.  The first ``while'' loop
of a {\em heap\_delete\_max\_max\/} takes time proportional to 
$\Phi_{i-1} - \Phi_i$ and the second ``while'' loop
requires that we touch $d_2$ vertex lists, where $d_2$ is the uncolored degree 
of the vertex returned by {\em heap\_delete\_max\_max\/}.  Hence, the 
amortized time for a {\em heap\_delete\_max\_max\/} operation is
$a_i  =  \left(d_2 + \Phi_{i-1} - \Phi_i \right) + \Phi_i - \Phi_{i-1} = d_2$.
This gives us a $\Theta(m)$ implementation as before, since we do one 
{\em heap\_delete\_max\_max\/} call per vertex, so that
the total amortized time for these calls is bounded by $2m$.
\hfill $\Box$
\medskip

\subsection{Reduced Saturation}
We close this section with a new enhancement to the saturation algorithm that 
we call {\em reduced saturation}.  Reduced saturation is a melding of the 
smallest-last~\cite{DUN1976,MAT1983} and saturation heuristics.  Suppose that 
at step $i$ of the saturation algorithm, there exists an uncolored vertex, 
$v$, such that 
\[
deg_{U_i}(v) < k - d_i(v)
\]
where $k$ is the number of colors currently in use.  In this case, $v$ will be
assigned one of the current $k$ colors irregardless of the choice of colors 
later assigned to its uncolored neighbors.  Hence, we can remove $v$ from 
$U_i$ and color it last with respect to $U_i$ as per the smallest-last 
heuristic.  This reduction decreases the uncolored degree of $v$'s uncolored 
neighbors, making further reductions of the same type more likely.  Vertices 
removed in this manner are stacked and then colored in stack order once the 
saturation algorithm has completed.  

Reduced saturation can be implemented to run in $O(m + k^2)$ time using the 
saturation heap structure.  Note that a reduction can become possible for a 
vertex in only three ways:
\begin{enumerate}
\item We color a vertex and decrease the uncolored degree of a neighbor without
 increasing the saturation degree of the neighbor. 
\item We remove a vertex because of a previous reduction which decreases the
 uncolored degrees of its neighbors. 
\item We introduce a new color which pushes the $k - d_i(v)$ difference 
above the uncolored degree of one or more vertices.
\end{enumerate}
The first two possibilities do not affect the running time of saturation since
they involve searching the set of uncolored neighbors of a vertex---something
that the saturation algorithm has to do anyway, even without this enhancement.
Saturation proper searches the uncolored neighborhood to update saturation 
weights while reduced saturation also searches the neighborhood for additional 
reductions.  In either case, the vertex is removed once the search is completed.
The third possibility requires that we check each vertex list associated with 
each \mbox{(saturation degree, uncolored degree)} pair, $(d_1, d_2)$, where 
$d_2 = \tilde{k} - d_1$ and $\tilde{k}$ is the old number of colors.  All 
vertices on any such nonempty list can be reduced. We need not check for 
$d_2 < \tilde{k} - d_1$ since these lists must be empty because of previous 
reductions.  Hence, introducing a new $i$-th color spawns a check for 
nonemptyness of $i$ vertex lists, which gives us the $k^2$ term.

\section{Polynomial Time Independent Set Selection}
In this section we describe the well known Approximate Maximal Independent Set
Selection (AMISS) and the Recursive Largest First (RLF) algorithms.  
The AMISS method proceeds 
by always selecting a vertex of minimal degree in the subgraph, 
$H_1$, induced by the set of all vertices that are not adjacent
to any vertex in the current independent being 
constructed (see Figure~\ref{fig:AMISS}).
We denote by $H_2$ the subgraph induced by all uncolored vertices that are 
adjacent to some vertex in the independent set under construction.  

The RLF algorithm, due 
to Leighton~\cite{LEI1979}, is a refinement of AMISS that incorporates the
largest-first heuristic, and gives better performance than
most sequential algorithms on many classes of graphs (see Figure~\ref{fig:RLF}).
Unlike AMISS, RLF chooses a vertex from $H_1$ that is adjacent to the largest
number of vertices in $H_2$, and breaks ties by choosing the vertex 
with minimal degree in $H_1$. This heuristic attempts to maximize 
the number of edges between vertices in the current independent set and vertices that 
remain uncolored after the independent set is removed.
These algorithms require that the second neighborhood of 
the vertex being colored (assigned to an independent set) be traversed 
to update the vertex degrees in $H_1$ and $H_2$; hence both
algorithms can require $O(n^3)$ time.  That is, if $k$ is the number
of colors used (independent sets constructed) and $d$ is the average 
vertex degree, then the total neighborhood traversal time is
proportional to $kdn$ or $km$, which can be as bad as $n^3$.  The time needed to
select the next vertex to add to the independent set under construction is 
pessimistically proportional to the number of uncolored 
vertices remaining, and so 
the overall runtime of both the AMISS and RLF algorithms is seen to belong to 
$O(km + n^2)$.  This bound 
is very pessimistic when the graph is sparse---while there is no
way to avoid traversing second neighborhoods, an implementation giving better 
bounds is possible.  We will require the following two additional saturation
heap routines:
\begin{list}{}
   {\setlength{\labelwidth}{1.75in}
    \setlength{\leftmargin}{1.75in}
    \setlength{\rightmargin}{0in}
    \setlength{\labelsep}{0in}
   }
\item[{\em heap\_delete\_max\_min\/$(h)$}\hfill]
--- A function that returns the vertex with minimal secondary key amongst those
vertices with maximal primary key in heap $h$, and removes that
vertex from~$h$.
\item[{\em heap\_delete\_min\_min\/$(h)$}\hfill]
--- A function that returns the vertex with minimal secondary key amongst those
vertices with minimal primary key in heap $h$, and removes that
vertex from~$h$.
\end{list}
Using our saturation heap given in Section~3 along with
the routines given in Figure~\ref{fig:MISSsatheap}, we claim a 
$O(km)$ runtime for both AMISS and RLF, giving an improvement on sparse graphs.
Figures~\ref{fig:AMISSsatheap}~and~\ref{fig:RLFsatheap} describe the use 
of the saturation heap in the AMISS and RLF algorithms, and 
theorems~\ref{thm:amiss}~and~\ref{thm:rlf} give our result with an 
amortized analysis (note that a weak saturation heap can be used
with the AMISS algorithm, but not with the RLF algorithm).

\newtheorem{amiss}{Theorem}[section]
\begin{amiss}
\label{thm:amiss}
The AMISS algorithm using a saturation heap as in 
Figure~\ref{fig:AMISSsatheap} runs in $O(km)$ time.
\end{amiss}

\noindent
{\bf Proof} \ \
In Figure~\ref{fig:AMISSsatheap}, the independent set being constructed is 
comprised of vertices assigned color $c$.  Every vertex is in exactly one of 
three states at any time: on the heap ($H_1$), on the vertex list ($H_2$), or 
already colored.  Only vertices on the heap can potentially be assigned to the 
current independent set (color class $c$) and vertices on the vertex list are
adjacent to some vertex that has already been assigned color $c$.  The uncolored
degree of each vertex is maintained so that the heap can be reinitialized to 
build each new independent set.  To get the $O(km)$ time bound, we do a simple 
amortized analysis (as in Section~3) to show that $O(m)$ time suffices to 
build each independent set. Define the potential function for the heap to be 
$\Phi_i = n - y_i$, where $y_i$ is the value of the saturation heap variable 
{\em minprimary\/} after the $i$-th heap operation.  The {\em create\_heap\/} 
operation requires $O(n)$ actual and amortized time and gets called only 
once.  The heap is reinitialized with a sequence of {\em heap\_insert\/} 
operations prior to the construction of each independent set.  This sequence 
of operations requires $O(n)$ actual and amortized time.  For each independent 
set, there can be no more than $O(n)$ {\em heap\_delete\/} and $O(m)$ 
{\em heap\_sift\/} operations, and both operations require only constant 
actual and amortized times.  The {\em heap\_delete\_min\_min\/} operation can 
require $O(n)$ actual time, $t_i$, but needs only constant amortized time, 
$a_i$, since
\begin{eqnarray*}
 a_i & = & t_i + \Phi_i - \Phi_{i-1} \\
     & = & (1 + y_i - y_{i-1}) + n - y_i  - (n - y_{i-1}) \\
     & = & 1.
\end{eqnarray*}
Since there are $n$ {\em heap\_delete\_min\_min\/} operations, only $O(n)$ 
amortized time is needed for all {\em heap\_delete\_min\_min\/} operations.  
Hence $O(m)$ amortized time suffices to build each independent set, giving an 
overall $O(km)$ implementation.
\hfill $\Box$
\medskip

\newtheorem{rlf}[amiss]{Theorem}
\begin{rlf}
\label{thm:rlf}
The RLF algorithm using a saturation heap as in Figure~\ref{fig:RLFsatheap} runs
in $O(km)$ time.
\end{rlf}

\noindent
{\bf Proof} \ \ 
Except for the {\em heap\_delete\_max\_max\/} and {\em heap\_delete\_max\_min\/}
operations, the proof is nearly identical to the proof of 
theorem~\ref{thm:amiss}.  We give an amortized analysis, using the value of 
the saturation heap variable, {\em maxprimary}, as our potential function, 
and we show that $O(m)$ time suffices to build each independent set.  The 
sequence of {\em heap\_insert\/} operations for each independent set needs 
only $O(n)$ actual and amortized time.  All {\em heap\_sift\/} and 
{\em heap\_delete\/} operations need only constant actual and amortized time 
and these operations are invoked at most $O(m)$ times per independent set.
There is but one call to {\em heap\_delete\_max\_max\/} per independent set and 
this call takes $O(n)$ actual and amortized time.  Finally, each call to 
{\em heap\_delete\_max\_min\/} requires amortized time proportional to the 
value of the secondary key of the vertex returned---this value is bounded 
above by the vertex degree in $G$, showing that $O(m)$ amortized time suffices
for all the {\em heap\_delete\_max\_min\/} operations used to build a single 
independent set (see the proof of theorem~\ref{strongthm}).
\hfill $\Box$
\medskip

\begin{thebibliography}{99}
  \bibitem{BRE1979}
    D. Br\'elaz.  1979.
    New Methods to Color Vertices of a Graph.
    {\em CACM},
    {\bf 22},
    251--256.
  \bibitem{DUN1976}
    F. D. J. Dunstan. 1976.
    Sequential Colourings of Graphs.
    {\em Cong.\ Num.},
    {\bf 15},
    151--158.
  \bibitem{JOH1990}	
    D. S. Johnson, C. R. Aragon, L. A. McGeoch and C. Schevon.
    Optimization by Simulated Annealing: An Experimental Evaluation, 
    Part II (Graph Coloring and Number Partitioning).  
    To appear in {\em Oper.\ Res.}
  \bibitem{KUB1985}
     M. Kubale and B. Jackowski. 1985.
     A Generalized Implicit Enumeration for Graph Coloring.
     {\em CACM},
     {\bf 28},
     412--418.
  \bibitem{LEI1979}
    F. T. Leighton.  1979.
    A Graph Coloring Algorithm for Large Scheduling Problems.
    {\em J. Res.\ Nat.\ Bur.\ Standards}
    {\bf 84},
    489--506.
  \bibitem{MAT1983}	
    D. W. Matula and L. L. Beck.  1983.  
    Smallest-Last Ordering and Clustering and Graph Coloring Algorithms.  
    {\em JACM.}, 
    {\bf 30}, 
    417--427.
  \bibitem{MOR1988}
    C. Morgenstern.  1988.
    Saturation Based Graph Coloring Algorithms.
    Tech Report CS88-1, University of New Mexico,
    Albuquerque, New Mexico.
  \bibitem{MOR1991} 
    C. Morgenstern and H. Shapiro.  1991.
    Heuristics for Rapidly Four-Coloring Large Planar Graphs.
    To appear in {\em Algorithmica}.
  \bibitem{MOR1990}
    C. Morgenstern.  1990.
    Algorithms for General Graph Coloring.
    PhD Dissertation, University of New Mexico,
    Albuquerque, New Mexico.
  \bibitem{SPI1985}	
    J. P. Spinrad and G. Vijayan.  1985.  
    Worst Case Analysis of a Graph Coloring Algorithm.  
    {\em Discrete Appl. Math.},
    {\bf 12}, 
    89--92.
  \bibitem{TUR1988}	
    J. S. Turner.  1988.  
    Almost All $k$-Colorable Graphs Are Easy to Color.  
    {\em J. Algorithms},
    {\bf 9}, 
    63--82.
\end{thebibliography}

\newpage
\begin{figure}
\begin{center}
\begin{tabular}{|p{3.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \kill
select a permutation, $\sigma$, of $[n]$; \\
for $i := 1$ to $n$ do \+ \\
   begin \+ \\
     select some $c \in \{\,\mbox{colors not assigned to any colored neighbor
     of $\sigma(i)$}\,\}$; \\
     assign color $c$ to vertex $\sigma(i)$ \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Sequential Coloring Algorithm}
\label{fig:Seq}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
var \+ \\
    $v, w, c \: : \: 0\ldots n$; \\
    $h \: :$ max priority queue; \- \\ \\
begin \+ \\
  (* initialize *) \\
  create\_heap$(h)$; \\
  for $v := 1$ to $n$ do \+ \\
    begin \+ \\
\<\<\<(**)\>\>\>
       create\_avail$(v,n)$; \\
       heap\_insert$(h,v,0,deg_G(v))$ \- \\
    end; \- \\ \\
  (* vertex coloring loop *) \\
  while not empty\_heap$(h)$ do \+ \\
    begin \+ \\
      (* $v$ in $U_i$ has maximal $D_i$ *) \\
      $v :=$ heap\_delete\_max\_max$(h)$; \\ \\
      (* greedy color assignment *) \\
      $c :=$ min\_avail$(v)$;  \\ \\
      color of $v := c$; \\
      for all $w \in N_{U_i}(v)$ do \+ \\
        (* update $D_{i+1}(w)$ *) \\
\<\<\<\<(***)\>\>\>\>
        if is\_avail$(w,c)$ then \+ \\
          begin \+ \\
            delete\_avail$(w,c)$; \\
            heap\_sift$(h,w,1,-1)$ \- \\
          end \- \\
        else heap\_sift$(h,w,0,-1)$ \- \- \\
     end \- \- \\
end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Saturation Algorithm}
\label{fig:SAT}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
type \+ \\
   lazy\_array $=$ record \+ \+ \+ \+ \+ \\
         time : $0 \ldots n$; \\
         where\_touched : array $[1 \ldots n]$ of $1 \ldots n$; \\
         time\_touched : array $[1 \ldots n]$ of $1 \ldots n$ \- \\
   end; \- \- \- \- \- \\ \\
procedure create\_lazy\_array(var $L$ : lazy\_array); \+ \\
   begin \+ \\
     $L$.time $:= 0$ \- \\
   end; \- \\ \\
function touched(var $L$ : lazy\_array; $a : 1 \ldots n$) : boolean; \+ \\
   var $t$ : boolean; \\
   begin \+ \\
     (* Has address $a$ been touched yet? *) \\
     with $L$ do \+ \\
        begin \+ \\
          $t :=$ (time\_touched$[a] \geq 1$) and (time\_touched$[a] \leq$ time); \\
          if $t$ then $t :=$ where\_touched$[$time\_touched$[a]] = a$; \\
          touched $:= t$ \- \\
        end \-\- \\
   end; \- \\ \\
procedure touch(var $L$ : lazy\_array; $a : 1 \ldots n$); \+ \\
   begin \+ \\
     (* Touch $a$ for the first time or just return. *) \\
     with $L$ do \+ \\
        if not touched$(L,a)$ then \+ \\
          begin \+ \\
            time $:=$ time $+ 1$; \\
            time\_touched$[a] :=$ time; \\
            where\_touched$[$time$] := a$ \- \\
          end \-\-\- \\
   end; 
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Lazy Array}
\label{fig:LZ}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
var \+ \\
   avail\_set $:$ array $[1 \ldots n]$ of lazy\_array; \- \\ \\
procedure create\_avail($v, n$); \+ \\
   begin \+ \\
     create\_lazy\_array(avail\_set$[v]$) \- \\
   end; \- \\ \\
function min\_avail$(v : 1 \ldots n) : 1 \dots n$; \+ \\
   var $c : 1 \ldots n$; \\
   begin \+ \\
     $c := 1$; \\
     while touched(avail\_set$[v], c$) do $c := c + 1$; \\
     min\_avail $:= c$ \- \\
   end; \- \\ \\
function is\_avail$(v, c : 1 \ldots n)$ : boolean; \+ \\
   begin \+ \\
     is\_avail $:=$ not touched(avail\_set$[v], c$) \- \\
   end; \- \\ \\
procedure delete\_avail$(v, c : 1 \ldots n)$; \+ \\
   begin \+ \\
     touch(avail\_set$[v], c$) \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Lazy Array Available Sets}
\label{fig:LZsets}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
const \+ \\
  nil $= 0$; \- \\
type \+ \\
  labels $=$ nil$\ldots n$; \\
  larray $=$ array [labels] of labels; \\
  vlist $=$ labels; \- \\
var \+ \\
   left, right : larray; \- \\ \\
procedure create\_vlist(var $L$ : vlist); \+ \\
   begin \+ \\
     $L :=$ nil \- \\
   end; \- \\ \\
function empty\_vlist($L$ : vlist) : boolean; \+ \\
   begin \+ \\
     empty\_vlist $:= L = \mbox{nil}$ \- \\
   end; \- \\ \\
function vlist\_select($L$ : vlist) : labels; \+ \\
   begin \+ \\
     vlist\_select $:= L$ \- \\
   end; \- \\ \\
procedure vlist\_insert(var $L$ : vlist; \ $v$ : labels); \+ \\
   begin \+ \\
     left$[v] :=$ nil; \\
     right$[v] := L$; \\
     if $L \neq \mbox{nil}$ then left$[L] := v$; \\
     $L := v$ \- \\
   end; \- \\ \\
procedure vlist\_delete(var $L$ : vlist; \ $v$ : labels); \+ \\
   begin\+ \\
     if left$[v] = \mbox{nil}$ then $L :=$ right$[v]$; \\
     if left$[v] \neq \mbox{nil}$ then right$[$left$[v]] :=$ right$[v]$; \\
     if right$[v] \neq \mbox{nil}$ then left$[$right$[v]] :=$ left$[v]$ \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Vertex Lists}
\label{fig:vlist}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
type \+ \\
   satheap $=$ record \+ \+ \+ \+ \\
        heap : array$[0 \ldots n]$ of vlist; \\
        primary\_deg : array$[1 \ldots n]$ of $0 \ldots n$; \\
        size, maxprimary, minprimary : $0 \ldots n$ \- \\
      end; \- \- \- \- \\ \\
procedure create\_heap(var $h$ : satheap); \+ \\
   var $i : 0 \ldots n$; \\
   begin \+ \\
     with $h$ do begin \+ \\
         size $:= 0$; \\ maxprimary $:= 0$; \\ minprimary $:= n$; \\
         for $i := 0$ to $n$ do create\_vlist(heap$[i]$) \- \\
       end \- \\
   end; \- \\ \\
function empty\_heap(var $h$ : satheap) : boolean; \+ \\
   begin \+ \\
     empty\_heap $:= h.\mbox{size} = 0$ \- \\
   end; \- \\ \\
procedure heap\_insert(var $h$ : satheap; \ 
                           $v : 1\ldots n$; \ $d_1, d_2 : 0\ldots n$); \+ \\
   (* Assumes that $v$ is not in the heap---ignores $d_2$. *) \\
   begin \+ \\
     with $h$ do begin \+ \\
         size $:= \mbox{size} + 1$; \\ 
	 primary\_deg$[v] := d_1$; \\
         vlist\_insert(heap$[d_1], v$); \\
         if $d_1 > \mbox{maxprimary}$ then maxprimary $:= d_1$; \\
         if $d_1 < \mbox{minprimary}$ then minprimary $:= d_1$ \- \\
       end \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Weak Saturation Heap}
\label{fig:wsatheap}
%\label{fig:wsatheap1}
\end{figure}
\clearpage

\addtocounter{figure}{-1}  % Continue previous figure

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
procedure heap\_delete(var $h$ : satheap; \ $v : 1\ldots n$);\+ \\
   (* Assumes that $v$ is in the heap *) \\
   begin \+ \\
     with $h$ do begin \+ \\
         size $:= \mbox{size} - 1$; \ \
         vlist\_delete(heap$[$primary\_deg$[v]]$, $v$) \- \\
       end \- \\
   end; \- \\ \\
procedure heap\_sift(var $h$ : satheap; \ 
                         $v : 1\ldots n$; \ $\delta_1, \delta_2 : -1\ldots 1$); \+ \\
   (* Assumes that $v$ is in the heap---ignores $\delta_2$. *) \\
   var $d : 0 \ldots n$; \\
   begin \+ \\
     with $h$ do begin \+ \\
         $d :=$ primary\_deg$[v] + \delta_1$; \\
         heap\_delete($h,v$); \\ 
         heap\_insert($h,v,d,0$) \- \\
       end \- \\
   end; \- \\ \\
function heap\_delete\_max\_max(var $h$ : satheap) : $1 \ldots n$; \+ \\
   (* Assumes that $h$ is not empty. *) \\
   var $v : 1 \ldots n$; \\ 
   begin \+ \\
     with $h$ do begin \+ \\
          while (empty\_vlist(heap[maxprimary])) do \+ \\
            maxprimary $:= \mbox{maxprimary} - 1$; \- \\
          $v :=$ vlist\_select(heap[maxprimary])); \\
          heap\_delete($h,v$); \\
          heap\_delete\_max\_max $:= v$ \- \\
       end \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Weak Saturation Heap (continued)}
%\label{fig:wsatheap2}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
type \+ \\
   satheap $=$ record \+ \\
        heap : array$[0 \ldots n]$ of array$[0 \ldots n]$ of vlist; \+ \\
          (* Heap$[i][j]$ contains a list of vertices with primary *) \\
          (* degree $i$ and secondary degree $j$. *) \- \\ \\
        lazy : array$[0 \ldots n]$ of lazy\_array; \+ \\
          (* Avoid an $O(n^2)$ explicit initialization of the heap. *) \- \\ \\
        nonempty : array$[0 \ldots n]$ of $0 \ldots n$; \+ \\
          (* Maintain number of nonempty vlists belonging to heap$[i]$. *) \- \\ \\
        primarydeg, secondarydeg : array$[1 \ldots n]$ of $0 \ldots n$; \+ \\
          (* Update the primary and secondary degrees of each vertex. *)\- \\ \\
        size, maxprimary, minprimary : $0 \ldots n$ \+ \\
          (* Size contains the number of vertices in the heap. *) \\
          (* No vertex has a larger primary degree than maxprimary. *) \\
          (* No vertex has a smaller primary degree than minprimary. *) \- \- \\
      end; \- \\ \\
procedure create\_heap(var $h$ : satheap); \+ \\
   var $i : 0 \ldots n$; \\
   begin \+ \\
     with $h$ do begin \+ \\
         size $:= 0$; \ \ maxprimary $:= 0$; \ \ minprimary $:= n$; \\
         for $i := 0$ to $n$ do \+ \\
           begin \+ \\
             create\_lazy\_array(lazy$[i]$); \\ nonempty$[i] := 0$ \- \\
           end \- \- \\
       end \- \\
   end; \- \\ \\
function empty\_heap(var $h$ : satheap) : boolean; \+ \\
   begin \+ \\
     empty\_heap $:= h.\mbox{size} = 0$ \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Saturation Heap}
\label{fig:satheap}
%\label{fig:satheap1}
\end{figure}
\clearpage

\addtocounter{figure}{-1}  % continue previous figure

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
procedure heap\_insert(var $h$ : satheap; \ 
                           $v : 1\ldots n$; \ $d_1, d_2 : 0\ldots n$); \+ \\
   (* Assumes that $v$ is not in the heap *) \\
   begin \+ \\
     with $h$ do begin \+ \\
         if not touched(lazy$[d_1], d_2$) then \+ \\
            begin \+ \\
              (* Only initialize as necessary. *) \\
              touch(lazy$[d_1], d_2$); \\ create\_vlist(heap$[d_1][d_2]$) \- \\
            end; \- \\
         if empty\_vlist(heap$[d_1][d_2]$) then \+ \\
	   nonempty$[d_1]$ $:=$ nonempty$[d_1] + 1$; \- \\
         vlist\_insert(heap$[d_1][d_2]$, $v$); \\
         size $:= \mbox{size} + 1$; \\ primarydeg$[v] := d_1$; \\ 
         secondarydeg$[v] := d_2$; \\
         if $d_1 > \mbox{maxprimary}$ then maxprimary $:= d_1$; \\
         if $d_1 < \mbox{minprimary}$ then minprimary $:= d_1$ \- \\
       end \- \\
   end; \- \\ \\
procedure heap\_delete(var $h$ : satheap; \ $v : 1\ldots n$);\+ \\
   var $d_1, d_2 : 0 \ldots n$; \\ 
   (* Assumes that $v$ is in the heap *) \\
   begin \+ \\
     with $h$ do begin \+ \\
         size $:= \mbox{size} - 1$; \\ 
         $d_1 :=$ primarydeg$[v]$; \\ 
         $d_2 :=$ secondarydeg$[v]$; \\
         vlist\_delete(heap$[d_1][d_2]$, $v$); \\
         if empty\_vlist(heap$[d_1][d_2]$) then \+ \\
	   nonempty$[d_1]$ $:=$ nonempty$[d_1] - 1$ \- \- \\
       end \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Saturation Heap (continued)}
%\label{fig:satheap2}
\end{figure}
\clearpage

\addtocounter{figure}{-1}  % continue previous figure

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
procedure heap\_sift(var $h$ : satheap; \ 
                         $v : 1\ldots n$; \ $\delta_1, \delta_2 : -1\ldots 1$); \+ \\
   var $d_1, d_2 : 0 \ldots n$; \\ 
   (* Assumes that $v$ is in the heap. *) \\
   begin \+ \\
     with $h$ do begin \+ \\
         $d_1 :=$ primarydeg$[v] + \delta_1$; \\ 
         $d_2 :=$ secondarydeg$[v] + \delta_2$; \\
         heap\_delete($h,v$); \\
         heap\_insert($h,v,d_1,d_2$) \- \\
       end \- \\
   end; \- \\ \\
function heap\_delete\_max\_max(var $h$ : satheap) : $1 \ldots n$; \+ \\
   var $v, i, d_1, d_2 : 1 \ldots n$; \\ 
   (* Assumes that $h$ is not empty. *) \\
   begin \+ \\
     with $h$ do begin \+ \\
          while nonempty$[$maxprimary$] = 0$ do \+ \\
            maxprimary $:= \mbox{maxprimary} - 1$; \- \\
          $d_1 :=$ maxprimary; \\ $d_2 := 0$; \\ $i := 0$; \\
          while $i < \mbox{nonempty}[d_1]$ do \+ \\
             begin \+ \\
                if touched(lazy$[d_1], d_2$) CAND \+ \+ \\
		   not empty\_vlist(heap$[d_1][d_2]$) then \- \\ 
                   $i := i+1$;\-\\
                if $i < \mbox{nonempty}[d_1]$ then $d_2 := d_2 + 1$ \- \\
             end; \- \\
          $v :=$ vlist\_select(heap$[d_1][d_2]$); \\
          heap\_delete($h,v$); \\
          heap\_delete\_max\_max $:= v$ \- \\
       end \- \\
   end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The Saturation Heap (continued)}
%\label{fig:satheap2}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{3in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \kill
begin \+ \\
  $c := 1$; \ \  $H_1 := V(G)$; \ \ $H_2 := \emptyset$; \\
  while $(H_1 \neq \emptyset)$ do \+ \\
    begin \+ \\
\<\<\<(*)\>\>\>
      $v :=$ a vertex of minimal degree in $\left < H_1 \right >$; \\
      for all $w \in N_{H_1}(v)$ do \+ \\
        begin \+ \\
          $H_1 := H_1 - \{w\}$; \ \ $H_2 := H_2 \cup \{w\}$ \- \\
        end; \- \\
      $H_1 := H_1 - \{v\}$; \ \ color of $v := c$; \\
      if $(H_1 = \emptyset)$ then \+ \\
        begin \+ \\
          $c := c + 1$; \ \ $H_1 := H_2$; \ \ $H_2 := \emptyset$ \- \\
        end \- \- \\
    end \- \- \\
end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The AMISS Algorithm}
\label{fig:AMISS}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
Replace line (*) in Figure~\ref{fig:AMISS} with the following lines: \\ \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \kill
if there are no vertices colored $c$ then \+ \\
         $v :=$ a vertex of maximal degree in $\left < H_1 \right >$ \- \\
else \+ \\
         $v :=$ a vertex of $G$ in $H_1$ with the largest number of neighbors 
	 in $\left < H_2 \right >$, \\
         \ \ \ \ \ \ and in the event of ties, also with the smallest number of \\ 
	 \ \ \ \ \ \ neighbors in $\left < H_1 \right >$;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The RLF Algorithm}
\label{fig:RLF}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
function heap\_delete\_min\_min(var $h$ : satheap) : $1 \ldots n$; \+ \\
   var $v, d_1, d_2 : 1 \ldots n$; \\ 
   (* Assumes that $h$ is not empty. *) \\
   begin \+ \\
     with $h$ do begin \+ \\
          while nonempty$[$minprimary$] = 0$ do \+ \\
            minprimary $:= \mbox{minprimary} + 1$; \- \\
          $d_1 :=$ minprimary; \\ $d_2 := 0$; \\
          while not touched(lazy$[d_1], d_2$) COR empty\_vlist(heap$[d_1][d_2]$) do \+ \\
              $d_2 := d_2 + 1$; \- \\
          $v :=$ vlist\_select(heap$[d_1][d_2]$); \\
          heap\_delete($h,v$); \\
          heap\_delete\_min\_min $:= v$ \- \\
       end \- \\
   end; \- \\ \\
function heap\_delete\_max\_min(var $h$ : satheap) : $1 \ldots n$; \+ \\
   var $v, d_1, d_2 : 1 \ldots n$; \\ 
   (* Assumes that $h$ is not empty. *) \\
   begin \+ \\
     with $h$ do begin \+ \\
          while nonempty$[$maxprimary$] = 0$ do \+ \\
            maxprimary $:= \mbox{maxprimary} - 1$; \- \\
          $d_1 :=$ maxprimary; \\ $d_2 := 0$; \\
          while not touched(lazy$[d_1], d_2$) COR empty\_vlist(heap$[d_1][d_2]$) do \+ \\
              $d_2 := d_2 + 1$; \- \\
          $v :=$ vlist\_select(heap$[d_1][d_2]$); \\
          heap\_delete($h,v$); \\
          heap\_delete\_max\_min $:= v$ \- \\
       end \- \\
   end; 
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{Additional Saturation Heap Operations}
\label{fig:MISSsatheap}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \kill
var \+ \\
   l : vlist; \+ \\
       (* Vlist structure given in Figure~\ref{fig:vlist}; \+ \+ \\
	  corresponds to $H_2$ of Figure~\ref{fig:AMISS}. *) \- \- \- \\ \\
   h : satheap; \+ \\
       (* Satheap structure given in Figure~\ref{fig:satheap}; \+ \+ \\
          corresponds to $H_1$ of Figure~\ref{fig:AMISS}. *) \- \- \- \\ \\
   where : array $[1 \ldots n]$ of (onheap, onlist, colored); \+ \\
       (* Every vertex is either in $H_1$, $H_2$, or already assigned a color. *) \- \\ \\
   ucdeg : array $[1 \ldots n]$ of $1 \ldots n$; \+ \\
       (* The number of uncolored neighbors of each vertex. *) \-\- \\ \\ 
begin \+ \\
   $c := 1$; \\ create\_vlist$(l)$; \\ create\_heap$(h)$; \\
   for $v := 1$ to $n$ do \+ \\
     begin \+ \\
\<\<\<(*)\>\>\>
       heap\_insert$(h, v, deg_G(v), 0)$;\\ 
       where$[v] :=$ onheap; \\ 
       ucdeg$[v] := deg_G(v)$ \- \\
     end; \- \\ \\
     for $i := 1$ to $n$ do \+ \\
       begin  \+ \\ 
	 (* Color one vertex each time through this loop. *) \\
\<\<\<(**)\>\>\>
        $v :=$ heap\_delete\_min\_min$(h)$;\\ 
        color of $v := c$; \\ 
        where$[v] :=$ colored; 
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The AMISS Algorithm Using a Saturation Heap}
\label{fig:AMISSsatheap}
\end{figure}
\clearpage

\addtocounter{figure}{-1}

\begin{figure}
\begin{center}
\begin{tabular}{|p{4.5in}|} \hline
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \+ \+ \+ \+ \kill
        for all $w \in N_G(v)$ do \+ \\
          if where$[w]$ $\neq$ colored then \+ \\  
             begin  \+ \\ 
	       (* Ignore colored neighbors. *)  \\
               if where$[w]$ $=$ onheap then \+ \\
                  begin \+ \\ 
		    (* Heap vertices adjacent to v cannot be colored c. *) \\
                    heap\_delete$(h, w)$; \\ 
                    vlist\_insert$(l, w)$; \\ 
                    where$[w] :=$ onlist; \\
                    for all $x \in N_G(w)$ do  \+ \\
                      if where$[x]$ $=$ onheap then \+ \\
\<\<\<\<\<\<\<\<\<\<(***)\>\>\>\>\>\>\>\>\>\>
                         heap\_sift$(h, x, -1, 0)$ \- \- \- \\
                  end; \- \\
               ucdeg$[w] :=$ ucdeg$[w] - 1$ \- \\
            end; \- \- \\ \\
        if empty\_heap$(h)$ and not empty\_vlist$(l)$ then \+ \\
           begin \+ \\ 
	     (* Initialize for next independent set. *) \\
             $c := c + 1$; \\ 
             while not empty\_vlist$(l)$ do \+ \\
                begin \+ \\
                  $v :=$ vlist\_select$(l)$; \\
                  where$[v] :=$ onheap; \\  
                  vlist\_delete$(l, v)$; \\
\<\<\<\<\<\<\<(****)\>\>\>\>\>\>\>
                  heap\_insert$(h,\,v,\,\mbox{ucdeg}[v],\,0)$ \- \\
                end \- \- \\
           end \- \- \\
       end \ \ (* for $i := 1$ to $n$ do *)  \- \- \\
end;
\end{tabbing}
\\ \hline
\end{tabular}
\end{center}
\caption{The AMISS Algorithm Using a Saturation Heap (continued)}
%\label{fig:AMISSsatheap}
\end{figure}
\clearpage

\begin{figure}
\begin{center}
\begin{tabular}{|l||p{3.5in}|} \hline
\multicolumn{2}{|l|}{Replace lines (*), (**), (***), and (****)
in Figure~\ref{fig:AMISSsatheap} as follows:} \\ \hline \hline
(*) & heap\_insert$(h, v, 0, deg_G(v))$ \\ \hline
(**) &
\begin{tabbing}
xx\=xx\=xx\=xx\=xx\=xx\=xx\=xx\= \kill
if there are no vertices colored $c$ then \+ \\
   $v :=$ heap\_delete\_max\_max$(h)$\- \\
else \+ \\ 
   $v :=$ heap\_delete\_max\_min$(h)$
\end{tabbing}
\\ \hline
(***) & heap\_sift$(h, x, 1, -1)$ \\ \hline
(****) & heap\_insert$(h,\,v,\,0,\,\mbox{ucdeg}[v])$ \\ \hline
\end{tabular}
\end{center}
\caption{The RLF Algorithm Using a Saturation Heap}
\label{fig:RLFsatheap}
\end{figure}
\end{document}
