1.1 --- a/damecco.tex Tue Nov 22 19:30:15 2016 +0100
1.2 +++ b/damecco.tex Wed Nov 23 02:07:56 2016 +0100
1.3 @@ -75,6 +75,8 @@
1.4 \let\oldproofname=\proofname
1.5 %% \renewcommand{\proofname}{\rm\bf{Proof:}}
1.6
1.7 +\captionsetup{font=normalsize}
1.8 +
1.9 \journal{Discrete Applied Mathematics}
1.10
1.11 \begin{document}
1.12 @@ -927,7 +929,7 @@
1.13 \end{example}
1.14
1.15 These examples may look artificial, but the same problems also appear
1.16 -in real-world examples, even though in a less obvious way.
1.17 +in real-world instances, even though in a less obvious way.
1.18
1.19 \subsection{Total ordering}
1.20 Instead of the total ordering relation, the matching order will be
1.21 @@ -1055,7 +1057,7 @@
1.22
1.23 \subsubsection{Subgraph isomorphism}
1.24 \begin{claim}
1.25 -\[LabCut_{IND}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\] is a cutting function by SUB.
1.26 +\[LabCut_{SUB}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!<\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\] is a cutting function by SUB.
1.27 \end{claim}
1.28
1.29
1.30 @@ -1276,8 +1278,8 @@
1.31 \subsection{Biological graphs}
1.32 The tests have been executed on a recent biological dataset created
1.33 for the International Contest on Pattern Search in Biological
1.34 -Databases\cite{Content}, which has been constructed of Molecule,
1.35 -Protein and Contact Map graphs extracted from the Protein Data
1.36 +Databases\cite{Content}, which has been constructed of molecule,
1.37 +protein and contact map graphs extracted from the Protein Data
1.38 Bank\cite{ProteinDataBank}.
1.39
1.40 The molecule dataset contains small graphs with less than 100 nodes
1.41 @@ -1289,16 +1291,121 @@
1.42 In the following, the induced subgraph isomorphism and the graph
1.43 isomorphism will be examined.
1.44
1.45 -\subsubsection{Induced subgraph isomorphism}
1.46 -This dataset contains a set of graph pairs, and \textbf{all} the
1.47 -induced subgraph ismorphisms have to be found between
1.48 -them. Figure~\ref{fig:INDProt}, \ref{fig:INDContact}, and
1.49 -\ref{fig:INDMolecule} show the solution time of the
1.50 -problems in the problem set.
1.51 +This dataset provides graph pairs, between which all the induced subgraph isomorphisms have to be found. For run time results, please see Figure~\ref{fig:bioIND}.
1.52 +
1.53 +In an other experiment, the nodes of each graph in the database had been
1.54 +shuffled, and an isomorphism between the shuffled and the original
1.55 +graph was searched. The solution times are shown on Figure~\ref{fig:bioISO}.
1.56 +
1.57 +
1.58
1.59 \begin{figure}[H]
1.60 +\vspace*{-2cm}
1.61 +\hspace*{-1.5cm}
1.62 +\begin{subfigure}[b]{0.55\textwidth}
1.63 +\begin{figure}[H]
1.64 +\begin{tikzpicture}[trim axis left, trim axis right]
1.65 +\begin{axis}[title=Molecules ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.66 +=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.67 + west},scaled x ticks = false,x tick label style={/pgf/number
1.68 + format/1000 sep = \thinspace}]
1.69 +%\addplot+[only marks] table {proteinsOrig.txt};
1.70 +\addplot table {Orig/moleculesIso.txt}; \addplot[mark=triangle*,mark
1.71 + size=1.8pt,color=red] table {VF2PPLabel/moleculesIso.txt};
1.72 +\end{axis}
1.73 +\end{tikzpicture}
1.74 +\caption{In the case of molecules, there is not such a significant
1.75 + difference, but VF2++ seems to be faster as the number of nodes
1.76 + increases.}\label{fig:ISOMolecule}
1.77 +\end{figure}
1.78 +\end{subfigure}
1.79 +\hspace*{1.5cm}
1.80 +\begin{subfigure}[b]{0.55\textwidth}
1.81 +\begin{figure}[H]
1.82 +\begin{tikzpicture}[trim axis left, trim axis right]
1.83 +\begin{axis}[title=Contact maps ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.84 +=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.85 + west},scaled x ticks = false,x tick label style={/pgf/number
1.86 + format/1000 sep = \thinspace}]
1.87 +%\addplot+[only marks] table {proteinsOrig.txt};
1.88 +\addplot table {Orig/contactMapsIso.txt}; \addplot[mark=triangle*,mark
1.89 + size=1.8pt,color=red] table {VF2PPLabel/contactMapsIso.txt};
1.90 +\end{axis}
1.91 +\end{tikzpicture}
1.92 +\caption{The results are closer to each other on contact maps, but
1.93 + VF2++ still performs consistently better.}\label{fig:ISOContact}
1.94 +\end{figure}
1.95 +\end{subfigure}
1.96 +
1.97 \begin{center}
1.98 -\begin{tikzpicture}
1.99 +\vspace*{-0.5cm}
1.100 +\begin{subfigure}[b]{0.55\textwidth}
1.101 +\begin{figure}[H]
1.102 +\begin{tikzpicture}[trim axis left, trim axis right]
1.103 +\begin{axis}[title=Proteins ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.104 +=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.105 + west},scaled x ticks = false,x tick label style={/pgf/number
1.106 + format/1000 sep = \thinspace}]
1.107 +%\addplot+[only marks] table {proteinsOrig.txt};
1.108 +\addplot table {Orig/proteinsIso.txt}; \addplot[mark=triangle*,mark
1.109 + size=1.8pt,color=red] table {VF2PPLabel/proteinsIso.txt};
1.110 +\end{axis}
1.111 +\end{tikzpicture}
1.112 +\caption{On protein graphs, VF2 Plus has a super linear time
1.113 + complexity, while VF2++ runs in near constant time. The difference
1.114 + is about two order of magnitude on large graphs.}\label{fig:ISOProt}
1.115 +\end{figure}
1.116 +\end{subfigure}
1.117 +\end{center}
1.118 +\vspace*{-0.6cm}
1.119 +\caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioISO}
1.120 +\end{figure}
1.121 +
1.122 +
1.123 +\begin{figure}[H]
1.124 +\vspace*{-2cm}
1.125 +\hspace*{-1.5cm}
1.126 +\begin{subfigure}[b]{0.55\textwidth}
1.127 +\begin{figure}[H]
1.128 +\begin{tikzpicture}[trim axis left, trim axis right]
1.129 +\begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.130 +=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.131 + west},scaled x ticks = false,x tick label style={/pgf/number
1.132 + format/1000 sep = \thinspace}]
1.133 +%\addplot+[only marks] table {proteinsOrig.txt};
1.134 +\addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
1.135 + size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
1.136 +\end{axis}
1.137 +\end{tikzpicture}
1.138 +\caption{In the case of molecules, the algorithms have
1.139 + similar behaviour, but VF2++ is almost two times faster even on such
1.140 + small graphs.} \label{fig:INDMolecule}
1.141 +\end{figure}
1.142 +\end{subfigure}
1.143 +\hspace*{1.5cm}
1.144 +\begin{subfigure}[b]{0.55\textwidth}
1.145 +\begin{figure}[H]
1.146 +\begin{tikzpicture}[trim axis left, trim axis right]
1.147 +\begin{axis}[title=Contact maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.148 +=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.149 + west},scaled x ticks = false,x tick label style={/pgf/number
1.150 + format/1000 sep = \thinspace}]
1.151 +%\addplot+[only marks] table {proteinsOrig.txt};
1.152 +\addplot table {Orig/ContactMaps.128.txt};
1.153 +\addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.154 + {VF2PPLabel/ContactMaps.128.txt};
1.155 +\end{axis}
1.156 +\end{tikzpicture}
1.157 +\caption{On contact maps, VF2++ runs in near constant time, while VF2
1.158 + Plus has a near linear behaviour.} \label{fig:INDContact}
1.159 +\end{figure}
1.160 +\end{subfigure}
1.161 +
1.162 +\begin{center}
1.163 +\vspace*{-0.5cm}
1.164 +\begin{subfigure}[b]{0.55\textwidth}
1.165 +\begin{figure}[H]
1.166 +\begin{tikzpicture}[trim axis left, trim axis right]
1.167 \begin{axis}[title=Proteins IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.168 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.169 west},scaled x ticks = false,x tick label style={/pgf/number
1.170 @@ -1308,114 +1415,18 @@
1.171 size=1.8pt,color=red] table {VF2PPLabel/Proteins.256.txt};
1.172 \end{axis}
1.173 \end{tikzpicture}
1.174 -\end{center}
1.175 -\vspace*{-0.8cm}
1.176 \caption{Both the algorithms have linear behaviour on protein
1.177 graphs. VF2++ is more than 10 times faster than VF2
1.178 Plus.} \label{fig:INDProt}
1.179 \end{figure}
1.180 -
1.181 -\begin{figure}[H]
1.182 -\begin{center}
1.183 -\begin{tikzpicture}
1.184 -\begin{axis}[title=Contact Maps IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.185 -=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.186 - west},scaled x ticks = false,x tick label style={/pgf/number
1.187 - format/1000 sep = \thinspace}]
1.188 -%\addplot+[only marks] table {proteinsOrig.txt};
1.189 -\addplot table {Orig/ContactMaps.128.txt};
1.190 -\addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.191 - {VF2PPLabel/ContactMaps.128.txt};
1.192 -\end{axis}
1.193 -\end{tikzpicture}
1.194 +\end{subfigure}
1.195 \end{center}
1.196 -\vspace*{-0.8cm}
1.197 -\caption{On Contact Maps, VF2++ runs in near constant time, while VF2
1.198 - Plus has a near linear behaviour.} \label{fig:INDContact}
1.199 +\vspace*{-0.5cm}
1.200 +\caption{\normalsize{Graph isomomorphism on biological graphs}}\label{fig:bioIND}
1.201 \end{figure}
1.202
1.203 -\begin{figure}[H]
1.204 -\begin{center}
1.205 -\begin{tikzpicture}
1.206 -\begin{axis}[title=Molecules IND,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.207 -=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.208 - west},scaled x ticks = false,x tick label style={/pgf/number
1.209 - format/1000 sep = \thinspace}]
1.210 -%\addplot+[only marks] table {proteinsOrig.txt};
1.211 -\addplot table {Orig/Molecules.32.txt}; \addplot[mark=triangle*,mark
1.212 - size=1.8pt,color=red] table {VF2PPLabel/Molecules.32.txt};
1.213 -\end{axis}
1.214 -\end{tikzpicture}
1.215 -\end{center}
1.216 -\vspace*{-0.8cm}
1.217 -\caption{In the case of Molecules, the algorithms seem to have a
1.218 - similar behaviour, but VF2++ is almost two times faster even on such
1.219 - small graphs.} \label{fig:INDMolecule}
1.220 -\end{figure}
1.221
1.222
1.223 -\subsubsection{Graph ismorphism}
1.224 -In this experiment, the nodes of each graph in the database have been
1.225 -shuffled and an isomorphism between the shuffled and the original
1.226 -graph has been searched. For runtime results, see
1.227 -Figure~\ref{fig:ISOProt}, \ref{fig:ISOContact}, and
1.228 -\ref{fig:ISOMolecule}.
1.229 -
1.230 -\begin{figure}[H]
1.231 -\begin{center}
1.232 -\begin{tikzpicture}
1.233 -\begin{axis}[title=Proteins ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.234 -=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.235 - west},scaled x ticks = false,x tick label style={/pgf/number
1.236 - format/1000 sep = \thinspace}]
1.237 -%\addplot+[only marks] table {proteinsOrig.txt};
1.238 -\addplot table {Orig/proteinsIso.txt}; \addplot[mark=triangle*,mark
1.239 - size=1.8pt,color=red] table {VF2PPLabel/proteinsIso.txt};
1.240 -\end{axis}
1.241 -\end{tikzpicture}
1.242 -\end{center}
1.243 -\vspace*{-0.8cm}
1.244 -\caption{On protein graphs, VF2 Plus has a super linear time
1.245 - complexity, while VF2++ runs in near constant time. The difference
1.246 - is about two order of magnitude on large graphs.}\label{fig:ISOProt}
1.247 -\end{figure}
1.248 -
1.249 -\begin{figure}[H]
1.250 -\begin{center}
1.251 -\begin{tikzpicture}
1.252 -\begin{axis}[title=Contact Maps ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.253 -=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.254 - west},scaled x ticks = false,x tick label style={/pgf/number
1.255 - format/1000 sep = \thinspace}]
1.256 -%\addplot+[only marks] table {proteinsOrig.txt};
1.257 -\addplot table {Orig/contactMapsIso.txt}; \addplot[mark=triangle*,mark
1.258 - size=1.8pt,color=red] table {VF2PPLabel/contactMapsIso.txt};
1.259 -\end{axis}
1.260 -\end{tikzpicture}
1.261 -\end{center}
1.262 -\vspace*{-0.8cm}
1.263 -\caption{The results are closer to each other on Contact Maps, but
1.264 - VF2++ still performs consistently better.}\label{fig:ISOContact}
1.265 -\end{figure}
1.266 -
1.267 -\begin{figure}[H]
1.268 -\begin{center}
1.269 -\begin{tikzpicture}
1.270 -\begin{axis}[title=Molecules ISO,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.271 -=major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.272 - west},scaled x ticks = false,x tick label style={/pgf/number
1.273 - format/1000 sep = \thinspace}]
1.274 -%\addplot+[only marks] table {proteinsOrig.txt};
1.275 -\addplot table {Orig/moleculesIso.txt}; \addplot[mark=triangle*,mark
1.276 - size=1.8pt,color=red] table {VF2PPLabel/moleculesIso.txt};
1.277 -\end{axis}
1.278 -\end{tikzpicture}
1.279 -\end{center}
1.280 -\vspace*{-0.8cm}
1.281 -\caption{In the case of Molecules, there is not such a significant
1.282 - difference, but VF2++ seems to be faster as the number of nodes
1.283 - increases.}\label{fig:ISOMolecule}
1.284 -\end{figure}
1.285
1.286
1.287 \subsection{Random graphs}
1.288 @@ -1427,18 +1438,22 @@
1.289 To evaluate the efficiency of the algorithms in the case of graph
1.290 isomorphism, connected graphs of less than 20 000 nodes have been
1.291 considered. Generating a random graph and shuffling its nodes, an
1.292 -isomorphism had to be found. Figure \ref{fig:randISO5},
1.293 -\ref{fig:randISO10}, \ref{fig:randISO15}, \ref{fig:randISO35},
1.294 -\ref{fig:randISO45}, and \ref{fig:randISO100} show the runtime results
1.295 +isomorphism had to be found. Figure \ref{fig:randISO} shows the runtime results
1.296 on graph sets of various density.
1.297
1.298 +
1.299 +
1.300 +
1.301 \begin{figure}[H]
1.302 +\vspace*{-1.5cm}
1.303 +\hspace*{-1.5cm}
1.304 +\begin{subfigure}[b]{0.55\textwidth}
1.305 \begin{center}
1.306 \begin{tikzpicture}
1.307 -\begin{axis}[title={Random ISO, $\delta = 5$},xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.308 +\begin{axis}[title={Random ISO, $\delta = 5$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.309 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.310 west},scaled x ticks = false,x tick label style={/pgf/number
1.311 - format/1000 sep = \thinspace}]
1.312 + format/1000 sep = \space}]
1.313 %\addplot+[only marks] table {proteinsOrig.txt};
1.314 \addplot table {randGraph/iso/vf2pIso5_1.txt};
1.315 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.316 @@ -1446,17 +1461,15 @@
1.317 \end{axis}
1.318 \end{tikzpicture}
1.319 \end{center}
1.320 -\vspace*{-0.8cm}
1.321 -\caption{}\label{fig:randISO5}
1.322 -\end{figure}
1.323 -
1.324 -\begin{figure}[H]
1.325 +\end{subfigure}
1.326 +%\hspace{1cm}
1.327 +\begin{subfigure}[b]{0.55\textwidth}
1.328 \begin{center}
1.329 \begin{tikzpicture}
1.330 -\begin{axis}[title={Random ISO, $\delta = 10$},xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.331 +\begin{axis}[title={Random ISO, $\delta = 10$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.332 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.333 west},scaled x ticks = false,x tick label style={/pgf/number
1.334 - format/1000 sep = \thinspace}]
1.335 + format/1000 sep = \space}]
1.336 %\addplot+[only marks] table {proteinsOrig.txt};
1.337 \addplot table {randGraph/iso/vf2pIso10_1.txt};
1.338 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.339 @@ -1464,17 +1477,16 @@
1.340 \end{axis}
1.341 \end{tikzpicture}
1.342 \end{center}
1.343 -\vspace*{-0.8cm}
1.344 -\caption{}\label{fig:randISO10}
1.345 -\end{figure}
1.346 -
1.347 -\begin{figure}[H]
1.348 +\end{subfigure}
1.349 +%%\hspace{1cm}
1.350 +\hspace*{-1.5cm}
1.351 +\begin{subfigure}[b]{0.55\textwidth}
1.352 \begin{center}
1.353 \begin{tikzpicture}
1.354 -\begin{axis}[title={Random ISO, $\delta = 15$},xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.355 +\begin{axis}[title={Random ISO, $\delta = 15$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.356 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.357 west},scaled x ticks = false,x tick label style={/pgf/number
1.358 - format/1000 sep = \thinspace}]
1.359 + format/1000 sep = \space}]
1.360 %\addplot+[only marks] table {proteinsOrig.txt};
1.361 \addplot table {randGraph/iso/vf2pIso15_1.txt};
1.362 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.363 @@ -1482,17 +1494,14 @@
1.364 \end{axis}
1.365 \end{tikzpicture}
1.366 \end{center}
1.367 -\vspace*{-0.8cm}
1.368 -\caption{}\label{fig:randISO15}
1.369 -\end{figure}
1.370 -
1.371 -\begin{figure}[H]
1.372 + \end{subfigure}
1.373 + \begin{subfigure}[b]{0.55\textwidth}
1.374 \begin{center}
1.375 \begin{tikzpicture}
1.376 -\begin{axis}[title={Random ISO, $\delta = 35$},xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.377 +\begin{axis}[title={Random ISO, $\delta = 35$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.378 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.379 west},scaled x ticks = false,x tick label style={/pgf/number
1.380 - format/1000 sep = \thinspace}]
1.381 + format/1000 sep = \space}]
1.382 %\addplot+[only marks] table {proteinsOrig.txt};
1.383 \addplot table {randGraph/iso/vf2pIso35_1.txt};
1.384 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.385 @@ -1500,32 +1509,25 @@
1.386 \end{axis}
1.387 \end{tikzpicture}
1.388 \end{center}
1.389 -\vspace*{-0.8cm}
1.390 -\caption{}\label{fig:randISO35}
1.391 -\end{figure}
1.392 -
1.393 -\begin{figure}[H]
1.394 -\begin{center}
1.395 +\end{subfigure}
1.396 +\begin{subfigure}[b]{0.55\textwidth}
1.397 +\hspace*{-1.5cm}
1.398 \begin{tikzpicture}
1.399 -\begin{axis}[title={Random ISO, $\delta = 45$},xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.400 +\begin{axis}[title={Random ISO, $\delta = 45$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.401 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.402 west},scaled x ticks = false,x tick label style={/pgf/number
1.403 - format/1000 sep = \thinspace}]
1.404 + format/1000 sep = \space}]
1.405 %\addplot+[only marks] table {proteinsOrig.txt};
1.406 \addplot table {randGraph/iso/vf2pIso45_1.txt};
1.407 \addplot[mark=triangle*,mark size=1.8pt,color=red] table
1.408 {randGraph/iso/vf2ppIso45_1.txt};
1.409 \end{axis}
1.410 \end{tikzpicture}
1.411 -\end{center}
1.412 -\vspace*{-0.8cm}
1.413 -\caption{}\label{fig:randISO45}
1.414 -\end{figure}
1.415 -
1.416 -\begin{figure}[H]
1.417 -\begin{center}
1.418 +\end{subfigure}
1.419 +\hspace*{-1.5cm}
1.420 +\begin{subfigure}[b]{0.55\textwidth}
1.421 \begin{tikzpicture}
1.422 -\begin{axis}[title={Random ISO, $\delta = 100$},xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},grid
1.423 +\begin{axis}[title={Random ISO, $\delta = 100$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.424 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.425 west},scaled x ticks = false,x tick label style={/pgf/number
1.426 format/1000 sep = \thinspace}]
1.427 @@ -1535,12 +1537,21 @@
1.428 {randGraph/iso/vf2ppIso100_1.txt};
1.429 \end{axis}
1.430 \end{tikzpicture}
1.431 -\end{center}
1.432 +\end{subfigure}
1.433 \vspace*{-0.8cm}
1.434 -\caption{}\label{fig:randISO100}
1.435 +\caption{IND on graphs having an average degree of
1.436 + 5.}\label{fig:randISO}
1.437 \end{figure}
1.438
1.439
1.440 +
1.441 +
1.442 +
1.443 +
1.444 +
1.445 +
1.446 +
1.447 +
1.448 Considering the graph isomorphism problem, VF2++ consistently
1.449 outperforms its rival especially on sparse graphs. The reason for the
1.450 slightly super linear behaviour of VF2++ on denser graphs is the
1.451 @@ -1571,7 +1582,8 @@
1.452
1.453
1.454 \begin{figure}[H]
1.455 -\vspace*{-0.8cm}
1.456 +\vspace*{-1.5cm}
1.457 +\hspace*{-1.5cm}
1.458 \begin{subfigure}[b]{0.55\textwidth}
1.459 \begin{center}
1.460 \begin{tikzpicture}
1.461 @@ -1602,7 +1614,7 @@
1.462 \end{tikzpicture}
1.463 \end{center}
1.464 \end{subfigure}
1.465 -\hspace{1cm}
1.466 +\hspace*{-1.5cm}
1.467 \begin{subfigure}[b]{0.55\textwidth}
1.468 \begin{center}
1.469 \begin{tikzpicture}
1.470 @@ -1634,7 +1646,7 @@
1.471 \end{center}
1.472 \end{subfigure}
1.473 \begin{subfigure}[b]{0.55\textwidth}
1.474 -
1.475 +\hspace*{-1.5cm}
1.476 \begin{tikzpicture}
1.477 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.478 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.479 @@ -1647,6 +1659,7 @@
1.480 \end{axis}
1.481 \end{tikzpicture}
1.482 \end{subfigure}
1.483 + \hspace*{-1.5cm}
1.484 \begin{subfigure}[b]{0.55\textwidth}
1.485 \begin{tikzpicture}
1.486 \begin{axis}[title={Random IND, $\delta = 5$, $\rho = 0.95$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.487 @@ -1667,6 +1680,7 @@
1.488
1.489 \begin{figure}[H]
1.490 \begin{center}
1.491 +\hspace*{-2cm}
1.492 \begin{tikzpicture}
1.493 \begin{axis}[title={Rand IND Summary, $\delta = 5$, $\rho = 0.3, 0.6, 0.8, 0.95$},height=17cm,width=16cm,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},line width=0.8pt,grid
1.494 =major,mark size=1pt, legend style={at={(0,1)},anchor=north
1.495 @@ -1699,9 +1713,11 @@
1.496
1.497
1.498 \begin{figure}[H]
1.499 -\vspace*{-0.8cm}
1.500 +\vspace*{-1.5cm}
1.501 +\hspace*{-1.5cm}
1.502 \begin{subfigure}[b]{0.55\textwidth}
1.503 \begin{center}
1.504 +\hspace*{-0.5cm}
1.505 \begin{tikzpicture}
1.506 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.05$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.507 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.508 @@ -1717,6 +1733,7 @@
1.509 \end{subfigure}
1.510 \begin{subfigure}[b]{0.55\textwidth}
1.511 \begin{center}
1.512 + \hspace*{-0.5cm}
1.513 \begin{tikzpicture}
1.514 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.1$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.515 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.516 @@ -1730,7 +1747,7 @@
1.517 \end{tikzpicture}
1.518 \end{center}
1.519 \end{subfigure}
1.520 -\hspace{1cm}
1.521 +\hspace*{-1.5cm}
1.522 \begin{subfigure}[b]{0.55\textwidth}
1.523 \begin{center}
1.524 \begin{tikzpicture}
1.525 @@ -1761,8 +1778,8 @@
1.526 \end{tikzpicture}
1.527 \end{center}
1.528 \end{subfigure}
1.529 +\hspace*{-1.5cm}
1.530 \begin{subfigure}[b]{0.55\textwidth}
1.531 -
1.532 \begin{tikzpicture}
1.533 \begin{axis}[title={Random IND, $\delta = 10$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.534 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.535 @@ -1795,6 +1812,7 @@
1.536
1.537 \begin{figure}[H]
1.538 \begin{center}
1.539 +\hspace*{-2cm}
1.540 \begin{tikzpicture}
1.541 \begin{axis}[title={Rand IND Summary, $\delta = 10$, $\rho = 0.3, 0.6, 0.8, 0.95$},height=17cm,width=16cm,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},line width=0.8pt,grid
1.542 =major,mark size=1pt, legend style={at={(0,1)},anchor=north
1.543 @@ -1834,7 +1852,8 @@
1.544
1.545
1.546 \begin{figure}[H]
1.547 -\vspace*{-0.8cm}
1.548 +\vspace*{-1.5cm}
1.549 +\hspace*{-1.5cm}
1.550 \begin{subfigure}[b]{0.55\textwidth}
1.551 \begin{center}
1.552 \begin{tikzpicture}
1.553 @@ -1865,7 +1884,7 @@
1.554 \end{tikzpicture}
1.555 \end{center}
1.556 \end{subfigure}
1.557 -\hspace{1cm}
1.558 +\hspace*{-1.5cm}
1.559 \begin{subfigure}[b]{0.55\textwidth}
1.560 \begin{center}
1.561 \begin{tikzpicture}
1.562 @@ -1896,8 +1915,8 @@
1.563 \end{tikzpicture}
1.564 \end{center}
1.565 \end{subfigure}
1.566 +\hspace*{-1.5cm}
1.567 \begin{subfigure}[b]{0.55\textwidth}
1.568 -
1.569 \begin{tikzpicture}
1.570 \begin{axis}[title={Random IND, $\delta = 35$, $\rho = 0.8$},width=7.2cm,height=6cm,xlabel={target size},ylabel={time (ms)},ylabel near ticks,legend entries={VF2 Plus,VF2++},grid
1.571 =major,mark size=1.2pt, legend style={at={(0,1)},anchor=north
1.572 @@ -1930,6 +1949,7 @@
1.573
1.574 \begin{figure}[H]
1.575 \begin{center}
1.576 +\hspace*{-2cm}
1.577 \begin{tikzpicture}
1.578 \begin{axis}[title={Rand IND Summary, $\delta = 35$, $\rho = 0.3, 0.6, 0.8, 0.95$},height=17cm,width=16cm,xlabel={target size},ylabel={time (ms)},legend entries={VF2 Plus,VF2++},line width=0.8pt,grid
1.579 =major,mark size=1pt, legend style={at={(0,1)},anchor=north