Vf2++' SUB, ISO cutting rules removed
authorMadarasi Peter
Sat, 26 Nov 2016 00:15:22 +0100
changeset 168349e9e65e18
parent 15 196396ea94b5
child 17 909bcb203f25
Vf2++' SUB, ISO cutting rules removed
damecco.tex
     1.1 --- a/damecco.tex	Fri Nov 25 23:47:31 2016 +0100
     1.2 +++ b/damecco.tex	Sat Nov 26 00:15:22 2016 +0100
     1.3 @@ -832,8 +832,8 @@
     1.4  
     1.5  \subsection{Cutting rules}
     1.6  \label{VF2PPCuttingRules}
     1.7 -This section presents the cutting rules of VF2++, which are improved
     1.8 -by using extra information coming from the node labels.
     1.9 +This section presents the cutting rule of VF2++ in the case of IND, which is improved
    1.10 +by using extra information coming from the node labels. For other problem types, the rules can be formulated similarly.
    1.11  \begin{notation}
    1.12  Let $\mathbf{\Gamma_{small}^{l}(u)}:=\{\tilde{u} : lab(\tilde{u})=l
    1.13  \wedge \tilde{u}\in \Gamma_{small} (u)\}$ and
    1.14 @@ -842,22 +842,10 @@
    1.15  V_{large}$ and $l$ is a label.
    1.16  \end{notation}
    1.17  
    1.18 -\subsubsection{Induced subgraph isomorphism}
    1.19  \begin{claim}
    1.20  \[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)|\ \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| < |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by IND.
    1.21  \end{claim}
    1.22  
    1.23 -\subsubsection{Graph isomorphism}
    1.24 -\begin{claim}
    1.25 -\[LabCut_{ISO}((u,v),M(s))\!:=\!\!\!\!\!\bigvee_{l\ is\ label}\!\!\!\!\!\!\!|\Gamma_{large}^{l} (v) \cap T_{large}(s)|\!\neq\!|\Gamma_{small}^{l}(u)\cap T_{small}(s)|\  \vee\]\[\bigvee_{l\ is\ label} \newline |\Gamma_{large}^{l}(v)\cap \tilde{T}_{large}(s)| \neq |\Gamma_{small}^{l}(u)\cap \tilde{T}_{small}(s)|\] is a cutting function by ISO.
    1.26 -\end{claim}
    1.27 -
    1.28 -\subsubsection{Subgraph isomorphism}
    1.29 -\begin{claim}
    1.30 -\[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.31 -\end{claim}
    1.32 -
    1.33 -
    1.34  
    1.35  \subsection{Implementation details}
    1.36  This section provides a detailed summary of an efficient