1.1 --- a/damecco.tex	Wed Nov 23 18:59:25 2016 +0100
     1.2 +++ b/damecco.tex	Wed Nov 23 20:45:31 2016 +0100
     1.3 @@ -1059,24 +1059,12 @@
     1.4  Where $i\in\{0,1, ..,|G_{small}|-1\}$, $v\in V_{large}$ and $INVALID$
     1.5  means "no node".
     1.6  \subsubsection{Avoiding the recurrence}
     1.7 -Exploring the state space was described in a recursive fashion using
     1.8 -sets (see Algorithm~\ref{alg:VF2Pseu}), which makes the
     1.9 -algorithm easy to understand but does not show directly an efficient
    1.10 -way of implementation. The following approach avoiding recursion and
    1.11 -using lookup tables instead of sets is not only fast but has linear
    1.12 -space complexity as well.
    1.13 -
    1.14  The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
    1.15 -as a while loop, which has a loop counter $depth$ denoting the
    1.16 -all-time depth of the recursion.  Fixing a matching order, let $M$
    1.17 -denote the array storing the all-time mapping.  The initial state is
    1.18 -associated with the empty mapping, which means that $\forall i:
    1.19 -M[i]=INVALID$ and $depth=0$.  In case of a recursive call, $depth$ has
    1.20 -to be incremented, while in case of a return, it has to be
    1.21 -decremented.  Based on Claim~\ref{claim:claimCoverFromLeft},
    1.22 +as a \textit{while loop}, which has a loop counter $depth$ denoting the
    1.23 +all-time depth of the recursion. Fixing a matching order, let $M$
    1.24 +denote the array storing the all-time mapping. Based on Claim~\ref{claim:claimCoverFromLeft},
    1.25  $M$ is $INVALID$ from index $depth$+1 and not $INVALID$ before
    1.26 -$depth$, i.e. $\forall i: i < depth \Rightarrow M[i]\neq INVALID$ and
    1.27 -$\forall i: i > depth \Rightarrow M[i]= INVALID$. $M[depth]$ changes
    1.28 +$depth$. $M[depth]$ changes
    1.29  while the state is being processed, but the property is held before
    1.30  both stepping back to a predecessor state and exploring a successor
    1.31  state.
    1.32 @@ -1100,19 +1088,7 @@
    1.33  
    1.34  Having said that, an algorithm running in $\Theta(deg)$ time is
    1.35  describable if there exists a covered node in the component containing
    1.36 -$u$. In this case choose a covered neighbour $u'$ of $u$ arbitrarily
    1.37 ---- such a node exists based on
    1.38 -Claim~\ref{claim:MOclaim}. With all the candidates of $u$
    1.39 -being among the uncovered neighbours of $Pair(M,u')$, there are solely
    1.40 -$deg(Pair(M,u'))$ nodes to check.
    1.41 -
    1.42 -An easy trick is to choose an $u'$, for which
    1.43 -$|\{uncovered\ neighbours\ $ $of\ Pair(M,u')\}|$ is the smallest
    1.44 -possible.
    1.45 -
    1.46 -Note that if $u$ is the first node of its component, then all the
    1.47 -uncovered nodes of $G_{large}$ are candidates, so giving a sublinear
    1.48 -method is impossible.
    1.49 +$u$, and a linear one other wise.
    1.50  
    1.51  
    1.52  \subsubsection{Determining the node order}
    1.53 @@ -1121,22 +1097,13 @@
    1.54  
    1.55  For using lookup tables, the node labels are associated with the
    1.56  numbers $\{0,1,..,|K|-1\}$, where $K$ is the set of the labels. It
    1.57 -enables $F_\mathcal{M}$ to be stored in an array, for which
    1.58 -$F_\mathcal{M}[i]=F_\mathcal{M}(i)$ where $i=0,1,..,|K|-1$. At first,
    1.59 +enables $F_\mathcal{M}$ to be stored in an array. At first, the node order
    1.60  $\mathcal{M}=\emptyset$, so $F_\mathcal{M}[i]$ is the number of nodes
    1.61  in $V_{small}$ having label i, which is easy to compute in
    1.62  $\Theta(|V_{small}|)$ steps.
    1.63  
    1.64 -$\mathcal{M}\subseteq V_{small}$ can be represented as an array of
    1.65 -size $|V_{small}|$.
    1.66 -
    1.67 -The BFS tree is computed by using a FIFO data structure which is
    1.68 -usually implemented as a linked list, but one can avoid it by using
    1.69 -the array $\mathcal{M}$ itself. $\mathcal{M}$ contains all the nodes
    1.70 -seen before, a pointer shows where the first node of the FIFO is, and
    1.71 -another one shows where the next explored node has to be inserted. So
    1.72 -the nodes of each level of the BFS tree can be processed by
    1.73 -Algorithms~\ref{alg:VF2PPProcess1} in place by swapping nodes.
    1.74 +Representing $\mathcal{M}\subseteq V_{small}$ as an array of
    1.75 +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.
    1.76  
    1.77  After a node $u$ gets to the next place of the node order,
    1.78  $F_\mathcal{M}[lab[u]]$ has to be decreased by one, because there is
    1.79 @@ -1144,10 +1111,6 @@
    1.80  min selection sort is preferred which gives the elements from left to
    1.81  right in descending order, see Algorithm~\ref{alg:VF2PPProcess1}.
    1.82  
    1.83 -Note that the \textit{while loop} of Algorithm~\ref{alg:VF2PPPseu}
    1.84 -takes one iteration per graph component and the graphs in biology are
    1.85 -mostly connected.
    1.86 -
    1.87  \subsubsection{Cutting rules}
    1.88  In Section~\ref{VF2PPCuttingRules}, the cutting rules were
    1.89  described using the sets $T_{small}$, $T_{large}$, $\tilde T_{small}$
    1.90 @@ -1164,7 +1127,7 @@
    1.91  T_{large}(s)$, the first part of the cutting rules is checkable in
    1.92  $\Theta(deg)$ time by considering the proper signs of $L$. Setting $L$
    1.93  to zero takes $\Theta(deg)$ time again, which makes it possible to use
    1.94 -the same table through the whole algorithm.  The second part of the
    1.95 +the same table through the whole algorithm. The second part of the
    1.96  cutting rules can be verified using the same method with $\tilde
    1.97  T_{small}$ and $\tilde T_{large}$ instead of $T_{small}$ and
    1.98  $T_{large}$. Thus, the overall complexity is $\Theta(deg)$.