
diff -r 54e95bfead8c -r 1a4874982d84 damecco.tex
--- a/damecco.tex	Wed Nov 30 16:13:29 2016 +0100
+++ b/damecco.tex	Wed Nov 30 16:52:36 2016 +0100
@@ -274,7 +274,9 @@
 code --- has been published as a part of LEMON\cite{LEMON} open source
 graph library.
 
-\section{Problem Statement}
+Outline: Section~\ref{sec:ProbStat} defines the problems to be solved, Section~\ref{sec:VF2Alg} provides a description of VF2, Section~\ref{sec:VF2ppAlg} introduces VF2++, a new graph matching algorithm, Section~\ref{sec:VF2ppImpl} presents the details of an efficient implementation of VF2++, and Section~\ref{sec:ExpRes} compares VF2++ to a state of the art algorithm.
+
+\section{Problem Statement}\label{sec:ProbStat}
 This section provides a formal description of the problems to be
 solved.
 \subsection{Definitions}
@@ -340,17 +342,13 @@
 The \textbf{graph isomorphism problem} can be defined as induced
 subgraph matching problem where the sizes of the two graphs are equal.
 
-In addition to existence, it may be needed to show such a subgraph, or
-it may be necessary to list all of them.
+In addition, one may want to find a \textbf{single} mapping or \textbf{enumerate} all of them.
 
-It should be noted that some authors misleadingly refer to the term
+Note that some authors refer to the term
 \emph{subgraph isomorphism problem} as an \emph{induced subgraph
   isomorphism problem}.
 
-The following sections give the descriptions of VF2, VF2++, VF2 Plus
-and a particular comparison.
-
-\section{The VF2 Algorithm}
+\section{The VF2 Algorithm}\label{sec:VF2Alg}
 This algorithm is the basis of both the VF2++ and the VF2 Plus.  VF2
 is able to handle all the variations mentioned in Section
   \ref{sec:CommProb}.  Although it can also handle directed graphs,
@@ -549,7 +547,7 @@
   \tilde{T}_{1}(\mathfrak{m})|$ is a cutting function by $IND$.
 \end{claim}
 
-\section{The VF2++ Algorithm}
+\section{The VF2++ Algorithm}\label{sec:VF2ppAlg}
 Although any total ordering relation makes the search space of VF2 a
 tree, its choice turns out to dramatically influence the number of
 visited states. The goal is to determine an efficient one as quickly
@@ -564,18 +562,15 @@
 
 In addition to the usual subgraph isomorphism, specialized versions
 for induced subgraph isomorphism and for graph isomorphism have been
-designed. VF2++ has gained a runtime improvement of one order of
-magnitude respecting induced subgraph isomorphism and a better
-asymptotical behaviour in the case of graph isomorphism problem.
+designed.
 
-Note that a weaker version of the cutting rules and the more efficient
-candidate set calculating were described in \cite{VF2Plus}, too.
+Note that a weaker version of the cutting rules and an efficient
+candidate set calculating were described in \cite{VF2Plus}.
 
 It should be noted that all the methods described in this section are
-extendable to handle directed graphs and edge labels as well.\newline
-
+extendable to handle directed graphs and edge labels as well.
 The basic ideas and the detailed description of VF2++ are provided in
-the following.
+the following.\newline
 
 The goal is to find a matching order in which the algorithm is able to
 recognize inconsistency or prune the infeasible branches on the
@@ -624,11 +619,11 @@
 \newline
 $\mathcal{L}(v):=black$
 \newline
-$\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in (V_{1}\backslash
-\{u\})$
+$\mathcal{L}(\tilde{u}):=red \ \forall \tilde{u}\in V_{1}\backslash
+\{u\}$
 \newline
-$\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in (V_{2}\backslash
-\{v\})$
+$\mathcal{L}(\tilde{v}):=red \ \forall \tilde{v}\in V_{2}\backslash
+\{v\}$
 \newline
 
 Now, any mapping by $\mathcal{L}$ must contain $(u,v)$, since
@@ -732,7 +727,7 @@
 \caption{\hspace{.5cm}$The\ method\ for\ processing\ a\ level\ of\ the\ BFS\ tree$}\label{alg:VF2PPProcess1}
 \begin{algorithmic}[1]
 \Procedure{VF2++ProcessLevel}{$V_{d}$} \While{$V_d\neq\emptyset$}
-\State $m\in$ arg min$_{F_\mathcal{M}\circ\ \mathcal{L}}($ arg max$_{deg}($arg
+\State $m\in$ arg min$_{F_{\mathcal{M}\circ\ \mathcal{L}}}($ arg max$_{deg}($arg
 max$_{Conn_{\mathcal{M}}}(V_{d})))$ \State $V_d:=V_d\backslash m$
 \State Append node $m$ to the end of $\mathcal{M}$ \State Refresh
 $F_\mathcal{M}$ \EndWhile \EndProcedure
@@ -778,10 +773,10 @@
 
 
 
-\section{Implementation details}
+\section{Implementation details}\label{sec:VF2ppImpl}
 This section provides a detailed summary of an efficient
 implementation of VF2++.
-\subsubsection{Storing a mapping}
+\subsection{Storing a mapping}
 After fixing an arbitrary node order ($u_0, u_1, ..,
 u_{|G_{1}|-1}$) of $G_{1}$, an array $M$ is usable to store
 the current mapping in the following way.
@@ -794,7 +789,7 @@
 \]
 where $i\in\{0,1, ..,|G_{1}|-1\}$, $v\in V_{2}$ and $INV\!ALI\!D$
 means "no node".
-\subsubsection{Avoiding the recurrence}
+\subsection{Avoiding the recurrence}
 The recursion of Algorithm~\ref{alg:VF2Pseu} can be realized
 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$
@@ -811,7 +806,7 @@
 has been designed for biological- and sparse graphs, see the next
 section for details.
 
-\subsubsection{Calculating the candidates for a node}
+\subsection{Calculating the candidates for a node}
 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the
 task is not to maintain the candidate set, but to generate the
 candidate nodes in $G_{2}$ for a given node $u\in V_{1}$.  In
@@ -827,7 +822,7 @@
 $u$, and a linear one otherwise.
 
 
-\subsubsection{Determining the node order}
+\subsection{Determining the node order}
 This section describes how the node order preprocessing method of
 VF2++ can efficiently be implemented.
 
@@ -841,7 +836,7 @@
 Representing $\mathcal{M}\subseteq V_{1}$ as an array of
 size $|V_{1}|$, both the computation of the BFS tree, and processing its levels by Algorithm~\ref{alg:VF2PPProcess1} can be done inplace by swapping nodes.
 
-\subsubsection{Cutting rules}
+\subsection{Cutting rules}
 In Section~\ref{VF2PPCuttingRules}, the cutting rules were
 described using the sets $T_{1}$, $T_{2}$, $\tilde T_{1}$
 and $\tilde T_{2}$, which are dependent on the all-time mapping
@@ -876,7 +871,7 @@
 Using similar techniques, the consistency function can be evaluated in
 $\Theta(deg)$ steps, as well.
 
-\section{Experimental results}
+\section{Experimental results}\label{sec:ExpRes}
 This section compares the performance of VF2++ and VF2 Plus. According to
 our experience, both algorithms run faster than VF2 with orders of
 magnitude, thus its inclusion was not reasonable.




