294 \begin{definition}\label{sec:ismorphic} |
294 \begin{definition}\label{sec:ismorphic} |
295 $G_{1}$ and $G_{2}$ are \textbf{isomorphic} (by the node label $\mathcal{L}$) if $\exists \mathfrak{m}: |
295 $G_{1}$ and $G_{2}$ are \textbf{isomorphic} (by the node label $\mathcal{L}$) if $\exists \mathfrak{m}: |
296 V_{1} \longrightarrow V_{2}$ bijection, for which the |
296 V_{1} \longrightarrow V_{2}$ bijection, for which the |
297 following is true: |
297 following is true: |
298 \begin{center} |
298 \begin{center} |
299 $\forall u\in{V_{1}} : \mathcal{L}(u)=\mathcal{L}(\mathfrak{m}(u))$ and |
299 $\forall u\in{V_{1}} : \mathcal{L}(u)=\mathcal{L}(\mathfrak{m}(u))$ and\\ |
300 $\forall u,v\in{V_{1}} : (u,v)\in{E_{1}} \Leftrightarrow (\mathfrak{m}(u),\mathfrak{m}(v))\in{E_{2}}$ |
300 $\forall u,v\in{V_{1}} : (u,v)\in{E_{1}} \Leftrightarrow (\mathfrak{m}(u),\mathfrak{m}(v))\in{E_{2}}$ |
301 \end{center} |
301 \end{center} |
302 \end{definition} |
302 \end{definition} |
303 |
303 |
304 \begin{definition} |
304 \begin{definition} |
305 $G_{1}$ is a \textbf{subgraph} of $G_{2}$ (by the node label $\mathcal{L}$) if $\exists \mathfrak{m}: |
305 $G_{1}$ is a \textbf{subgraph} of $G_{2}$ (by the node label $\mathcal{L}$) if $\exists \mathfrak{m}: |
306 V_{1}\longrightarrow V_{2}$ injection, for which the |
306 V_{1}\longrightarrow V_{2}$ injection, for which the |
307 following is true: |
307 following is true: |
308 \begin{center} |
308 \begin{center} |
309 $\forall u\in{V_{1}} : \mathcal{L}(u)=\mathcal{L}(\mathfrak{m}(u))$ and |
309 $\forall u\in{V_{1}} : \mathcal{L}(u)=\mathcal{L}(\mathfrak{m}(u))$ and\\ |
310 $\mathbb{M}$ |
|
311 $\forall u,v \in{V_{1}} : (u,v)\in{E_{1}} \Rightarrow (\mathfrak{m}(u),\mathfrak{m}(v))\in E_{2}$ |
310 $\forall u,v \in{V_{1}} : (u,v)\in{E_{1}} \Rightarrow (\mathfrak{m}(u),\mathfrak{m}(v))\in E_{2}$ |
312 \end{center} |
311 \end{center} |
313 \end{definition} |
312 \end{definition} |
314 |
313 |
315 \begin{definition} |
314 \begin{definition} |
378 A mapping $\mathfrak{m}$ is $\mathbf{whole\ mapping}$ if $\mathfrak{m}$ covers all the |
377 A mapping $\mathfrak{m}$ is $\mathbf{whole\ mapping}$ if $\mathfrak{m}$ covers all the |
379 nodes of $V_{1}$, i.e. $\mathfrak{D}(\mathfrak{m})=V_1$. |
378 nodes of $V_{1}$, i.e. $\mathfrak{D}(\mathfrak{m})=V_1$. |
380 \end{definition} |
379 \end{definition} |
381 |
380 |
382 \begin{definition} |
381 \begin{definition} |
383 Let \textbf{extend}$(\mathfrak{m},(u,v))$ denote the function $f : \mathfrak{D}(\mathfrak{m})\cup\{u\}\longrightarrow\mathfrak{R}(\mathfrak{m})\cup\{v\}$, for which $\forall w\in \mathfrak{D}(\mathfrak{m}) : \mathfrak{m}(w)=f(w)$ and $f(u)=v$ holds. Where $u\notin\mathfrak{D}(\mathfrak{m})$ and $v\notin\mathfrak{R}(\mathfrak{m})$, otherwise $extend(\mathfrak{m},(u,v))$ is undefined. |
382 Let \textbf{extend}$(\mathfrak{m},(u,v))$ denote the function $f : \mathfrak{D}(\mathfrak{m})\cup\{u\}\longrightarrow\mathfrak{R}(\mathfrak{m})\cup\{v\}$, for which $\forall w\in \mathfrak{D}(\mathfrak{m}) : \mathfrak{m}(w)=f(w)$ and $f(u)=v$ holds. Where $u\in V_1\setminus\mathfrak{D}(\mathfrak{m})$ and $v\in V_2\setminus\mathfrak{R}(\mathfrak{m})$, otherwise $extend(\mathfrak{m},(u,v))$ is undefined. |
384 \end{definition} |
383 \end{definition} |
385 |
384 |
386 \begin{notation} |
385 \begin{notation} |
387 Throughout the paper, $\mathbf{PT}$ denotes a generic problem type |
386 Throughout the paper, $\mathbf{PT}$ denotes a generic problem type |
388 which can be substituted by any of the $\mathbf{ISO}$, $\mathbf{SUB}$ |
387 which can be substituted by any of the $\mathbf{ISO}$, $\mathbf{SUB}$ |
814 |
813 |
815 \subsubsection{Calculating the candidates for a node} |
814 \subsubsection{Calculating the candidates for a node} |
816 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the |
815 Being aware of Claim~\ref{claim:claimCoverFromLeft}, the |
817 task is not to maintain the candidate set, but to generate the |
816 task is not to maintain the candidate set, but to generate the |
818 candidate nodes in $G_{2}$ for a given node $u\in V_{1}$. In |
817 candidate nodes in $G_{2}$ for a given node $u\in V_{1}$. In |
819 case of any of the three problem types and a mapping $M$ if a node $v\in |
818 case of any of the three problem types and a mapping $\mathfrak{m}$, if a node $v\in |
820 V_{2}$ is a potential pair of $u\in V_{1}$, then $\forall |
819 V_{2}$ is a potential pair of $u\in V_{1}$, then $\forall |
821 u'\in V_{1} : (u,u')\in |
820 u'\in \mathfrak{D}(\mathfrak{m}) : (u,u')\in |
822 E_{1}\ and\ u'\ is\ covered\ by\ M\ \Rightarrow (v,Pair(M,u'))\in |
821 E_{1}\Rightarrow (v,\mathfrak{m}(u'))\in |
823 E_{2}$. That is, each covered neighbour of $u$ has to be mapped to |
822 E_{2}$. That is, each covered neighbour of $u$ has to be mapped to |
824 a covered neighbour of $v$. |
823 a covered neighbour of $v$. |
825 |
824 |
826 Having said that, an algorithm running in $\Theta(deg)$ time is |
825 Having said that, an algorithm running in $\Theta(deg)$ time is |
827 describable if there exists a covered node in the component containing |
826 describable if there exists a covered node in the component containing |