# HG changeset patch
# User Madarasi Peter
# Date 1479930331 -3600
# Node ID 2ad9aa6d7f63b16de244d4e5b4b3d92824b489e2
# Parent  49574b75404bafb6377c616641079ef9879a914e
The implementation details part has been shortened

diff -r 49574b75404b -r 2ad9aa6d7f63 damecco.tex
--- a/damecco.tex	Wed Nov 23 18:59:25 2016 +0100
+++ b/damecco.tex	Wed Nov 23 20:45:31 2016 +0100
@@ -1059,24 +1059,12 @@
 Where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
 means "no node".
 \subsubsection{Avoiding the recurrence}
-Exploring the state space was described in a recursive fashion using
-sets (see Algorithm~\ref{alg:VF2Pseu}), which makes the
-algorithm easy to understand but does not show directly an efficient
-way of implementation. The following approach avoiding recursion and
-using lookup tables instead of sets is not only fast but has linear
-space complexity as well.
-
 The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
-as a while loop, which has a loop counter $depth$ denoting the
-all-time depth of the recursion.  Fixing a matching order, let $M$
-denote the array storing the all-time mapping.  The initial state is
-associated with the empty mapping, which means that $\forall i:
-M[i]=INVALID$ and $depth=0$.  In case of a recursive call, $depth$ has
-to be incremented, while in case of a return, it has to be
-decremented.  Based on Claim~\ref{claim:claimCoverFromLeft},
+as a \textit{while loop}, which has a loop counter $depth$ denoting the
+all-time depth of the recursion. Fixing a matching order, let $M$
+denote the array storing the all-time mapping. Based on Claim~\ref{claim:claimCoverFromLeft},
 $M$ is $INVALID$ from index $depth$+1 and not $INVALID$ before
-$depth$, i.e. $\forall i: i < depth \Rightarrow M[i]\neq INVALID$ and
-$\forall i: i > depth \Rightarrow M[i]= INVALID$. $M[depth]$ changes
+$depth$. $M[depth]$ changes
 while the state is being processed, but the property is held before
 both stepping back to a predecessor state and exploring a successor
 state.
@@ -1100,19 +1088,7 @@
 
 Having said that, an algorithm running in $\Theta(deg)$ time is
 describable if there exists a covered node in the component containing
-$u$. In this case choose a covered neighbour $u'$ of $u$ arbitrarily
---- such a node exists based on
-Claim~\ref{claim:MOclaim}. With all the candidates of $u$
-being among the uncovered neighbours of $Pair(M,u')$, there are solely
-$deg(Pair(M,u'))$ nodes to check.
-
-An easy trick is to choose an $u'$, for which
-$|\{uncovered\ neighbours\ $ $of\ Pair(M,u')\}|$ is the smallest
-possible.
-
-Note that if $u$ is the first node of its component, then all the
-uncovered nodes of $G_{large}$ are candidates, so giving a sublinear
-method is impossible.
+$u$, and a linear one other wise.
 
 
 \subsubsection{Determining the node order}
@@ -1121,22 +1097,13 @@
 
 For using lookup tables, the node labels are associated with the
 numbers $\{0,1,..,|K|-1\}$, where $K$ is the set of the labels. It
-enables $F_\mathcal{M}$ to be stored in an array, for which
-$F_\mathcal{M}[i]=F_\mathcal{M}(i)$ where $i=0,1,..,|K|-1$. At first,
+enables $F_\mathcal{M}$ to be stored in an array. At first, the node order
 $\mathcal{M}=\emptyset$, so $F_\mathcal{M}[i]$ is the number of nodes
 in $V_{small}$ having label i, which is easy to compute in
 $\Theta(|V_{small}|)$ steps.
 
-$\mathcal{M}\subseteq V_{small}$ can be represented as an array of
-size $|V_{small}|$.
-
-The BFS tree is computed by using a FIFO data structure which is
-usually implemented as a linked list, but one can avoid it by using
-the array $\mathcal{M}$ itself. $\mathcal{M}$ contains all the nodes
-seen before, a pointer shows where the first node of the FIFO is, and
-another one shows where the next explored node has to be inserted. So
-the nodes of each level of the BFS tree can be processed by
-Algorithms~\ref{alg:VF2PPProcess1} in place by swapping nodes.
+Representing $\mathcal{M}\subseteq V_{small}$ as an array of
+size $|V_{small}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done inplace by swapping nodes.
 
 After a node $u$ gets to the next place of the node order,
 $F_\mathcal{M}[lab[u]]$ has to be decreased by one, because there is
@@ -1144,10 +1111,6 @@
 min selection sort is preferred which gives the elements from left to
 right in descending order, see Algorithm~\ref{alg:VF2PPProcess1}.
 
-Note that the \textit{while loop} of Algorithm~\ref{alg:VF2PPPseu}
-takes one iteration per graph component and the graphs in biology are
-mostly connected.
-
 \subsubsection{Cutting rules}
 In Section~\ref{VF2PPCuttingRules}, the cutting rules were
 described using the sets $T_{small}$, $T_{large}$, $\tilde T_{small}$
@@ -1164,7 +1127,7 @@
 T_{large}(s)$, the first part of the cutting rules is checkable in
 $\Theta(deg)$ time by considering the proper signs of $L$. Setting $L$
 to zero takes $\Theta(deg)$ time again, which makes it possible to use
-the same table through the whole algorithm.  The second part of the
+the same table through the whole algorithm. The second part of the
 cutting rules can be verified using the same method with $\tilde
 T_{small}$ and $\tilde T_{large}$ instead of $T_{small}$ and
 $T_{large}$. Thus, the overall complexity is $\Theta(deg)$.