830 provides a matching order. |
830 provides a matching order. |
831 |
831 |
832 |
832 |
833 \subsection{Cutting rules} |
833 \subsection{Cutting rules} |
834 \label{VF2PPCuttingRules} |
834 \label{VF2PPCuttingRules} |
835 This section presents the cutting rules of VF2++, which are improved |
835 This section presents the cutting rule of VF2++ in the case of IND, which is improved |
836 by using extra information coming from the node labels. |
836 by using extra information coming from the node labels. For other problem types, the rules can be formulated similarly. |
837 \begin{notation} |
837 \begin{notation} |
838 Let $\mathbf{\Gamma_{small}^{l}(u)}:=\{\tilde{u} : lab(\tilde{u})=l |
838 Let $\mathbf{\Gamma_{small}^{l}(u)}:=\{\tilde{u} : lab(\tilde{u})=l |
839 \wedge \tilde{u}\in \Gamma_{small} (u)\}$ and |
839 \wedge \tilde{u}\in \Gamma_{small} (u)\}$ and |
840 $\mathbf{\Gamma_{large}^{l}(v)}:=\{\tilde{v} : lab(\tilde{v})=l \wedge |
840 $\mathbf{\Gamma_{large}^{l}(v)}:=\{\tilde{v} : lab(\tilde{v})=l \wedge |
841 \tilde{v}\in \Gamma_{large} (v)\}$, where $u\in V_{small}$, $v\in |
841 \tilde{v}\in \Gamma_{large} (v)\}$, where $u\in V_{small}$, $v\in |
842 V_{large}$ and $l$ is a label. |
842 V_{large}$ and $l$ is a label. |
843 \end{notation} |
843 \end{notation} |
844 |
844 |
845 \subsubsection{Induced subgraph isomorphism} |
|
846 \begin{claim} |
845 \begin{claim} |
847 \[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. |
846 \[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. |
848 \end{claim} |
847 \end{claim} |
849 |
|
850 \subsubsection{Graph isomorphism} |
|
851 \begin{claim} |
|
852 \[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. |
|
853 \end{claim} |
|
854 |
|
855 \subsubsection{Subgraph isomorphism} |
|
856 \begin{claim} |
|
857 \[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. |
|
858 \end{claim} |
|
859 |
|
860 |
848 |
861 |
849 |
862 \subsection{Implementation details} |
850 \subsection{Implementation details} |
863 This section provides a detailed summary of an efficient |
851 This section provides a detailed summary of an efficient |
864 implementation of VF2++. |
852 implementation of VF2++. |