# HG changeset patch
# User Madarasi Peter
# Date 1479923965 -3600
# Node ID 49574b75404bafb6377c616641079ef9879a914e
# Parent  4989d677d5e34ecdab8fc1bddb5d62705326b328
Algorithm 4 removed

diff -r 4989d677d5e3 -r 49574b75404b damecco.tex
--- a/damecco.tex	Wed Nov 23 02:07:56 2016 +0100
+++ b/damecco.tex	Wed Nov 23 18:59:25 2016 +0100
@@ -944,8 +944,8 @@
 \end{definition}
 
 \begin{algorithm}
-\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
-nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..
+\algtext*{EndIf}
+\algtext*{EndProcedure}
 \algtext*{EndWhile}
 \caption{\hspace{0.5cm}$The\ method\ of\ VF2++\ for\ determining\ the\ node\ order$}\label{alg:VF2PPPseu}
 \begin{algorithmic}[1]
@@ -956,16 +956,16 @@
 \mathcal{M})$)\label{alg:findMin} \State Compute $T$, a BFS tree with
 root node $r$.  \For{$d=0,1,...,depth(T)$} \State $V_d$:=nodes of the
 $d$-th level \State Process $V_d$ \Comment{See Algorithm
-  \ref{alg:VF2PPProcess1}) and \ref{alg:VF2PPProcess2}} \EndFor
+  \ref{alg:VF2PPProcess1}} \EndFor
 \EndWhile \EndProcedure
 \end{algorithmic}
 \end{algorithm}
 
 \begin{algorithm}
-\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
-nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..
+\algtext*{EndIf}
+\algtext*{EndProcedure}%ne nyomtasson ..
 \algtext*{EndWhile}
-\caption{\hspace{.5cm}$A\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
+\caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
 \begin{algorithmic}[1]
 \Procedure{VF2++ProcessLevel1}{$V_{d}$} \While{$V_d\neq\emptyset$}
 \State $m\in$ arg min$_{F_\mathcal{M}\circ\ lab}($ arg max$_{deg}($arg
@@ -975,33 +975,13 @@
 \end{algorithmic}
 \end{algorithm}
 
-\begin{algorithm}
-\algtext*{EndIf}%ne nyomtasson end if-et \algtext*{EndFor}%ne
-nyomtasson ..  \algtext*{EndProcedure}%ne nyomtasson ..
-\algtext*{EndWhile}
-\caption{\hspace{0.5cm}$Another\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess2}
-\begin{algorithmic}[1]
-\Procedure{VF2++ProcessLevel2}{$V_{d}$} \State Sort $V_d$ in
-descending lex. order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$
-\State Append the sorted $V_d$ to the end of $\mathcal{M}$ \State
-Refresh $F_\mathcal{M}$ \EndProcedure
-\end{algorithmic}
-\end{algorithm}
 Algorithm~\ref{alg:VF2PPPseu} is a high level description of the
 matching order procedure of VF2++. It computes a BFS tree for each
 component in ascending order of their rarest $lab$ and largest $deg$,
 whose root vertex is the component's minimal
-node. Algorithms~\ref{alg:VF2PPProcess1} and \ref{alg:VF2PPProcess2}
-are two different methods to process a level of the BFS tree.
-
-After sorting the nodes of the current level in descending
-lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$,
-Algorithm~\ref{alg:VF2PPProcess2} appends them simultaneously to the
-matching order $\mathcal{M}$ and refreshes $F_\mathcal{M}$ just once,
-whereas Algorithm~\ref{alg:VF2PPProcess1} appends the nodes separately
-to $\mathcal{M}$ and refreshes $F_\mathcal{M}$ immediately, so it
-provides up-to-date label information and may result in a more
-efficient matching order.
+node. Algorithm~\ref{alg:VF2PPProcess1} is a method to process a level of the BFS tree, which appends the nodes of the current level in descending
+lexicographic order by $(Conn_{\mathcal{M}},deg,-F_\mathcal{M})$ separately
+to $\mathcal{M}$, and refreshes $F_\mathcal{M}$ immediately.
 
 Claim~\ref{claim:MOclaim} shows that Algorithm~\ref{alg:VF2PPPseu}
 provides a matching order.
@@ -1156,8 +1136,7 @@
 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} and
-\ref{alg:VF2PPProcess2} in place by swapping nodes.
+Algorithms~\ref{alg:VF2PPProcess1} in place 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
@@ -1165,15 +1144,6 @@
 min selection sort is preferred which gives the elements from left to
 right in descending order, see Algorithm~\ref{alg:VF2PPProcess1}.
 
-Note that using a $\Theta(n^2)$ sort absolutely does not slow down the
-procedure on biological (and on sparse) graphs, since they have few
-nodes on a level. If a level had a large number of nodes,
-Algorithm~\ref{alg:VF2PPProcess2} would seem to be a better
-choice with a $\Theta(nlog(n))$ or Bucket sort, but it may reduce the
-efficiency of the matching procedure, since $F_\mathcal{M}(i)$ can not
-be immediately refreshed, so it is unable to provide up-to-date label
-information.
-
 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.