Correct predictions are in blue. If we detect only a subset of a labelled sentence, we highlight the caught part as blue, the missing part light blue. False positives are in green and false negatives are in red.

Problem 114 (Subgraph Isomorphism) — Constraint detection

A subgraph isomorphism problem -LRB- SIP -RRB- between a pattern graph Gp = -LRB- Np , Ep -RRB- and a target graph Gt = -LRB- Nt , Et -RRB- consists in deciding whether Gp is isomorphic to some subgraph of Gt . More precisely , one should find an injective function $ f : Np \ to Nt $ that associates a different node of the target graph with every node of the pattern graph and that matches edges of the pattern graph , i.e. , $ \ forall -LRB- u , v -RRB- in Np \ times Np , -LRB- u , v -RRB- \ in Ep \ Rightarrow -LRB- f -LRB- u -RRB- , f -LRB- v -RRB- -RRB- \ in Et $ . Note that the subgraph is not necessarily induced so that two pattern nodes that are not linked by an edge may be matched to target nodes which are linked by an edge .

Problem 114 (Subgraph Isomorphism) — Detection of the decisions and objects to be modeled

A subgraph isomorphism problem -LRB- SIP -RRB- between a pattern graph Gp = -LRB- Np , Ep -RRB- and a target graph Gt = -LRB- Nt , Et -RRB- consists in deciding whether Gp is isomorphic to some subgraph of Gt . More precisely , one should find an injective function $ f : Np \ to Nt $ that associates a different node of the target graph with every node of the pattern graph and that matches edges of the pattern graph , i.e. , $ \ forall -LRB- u , v -RRB- in Np \ times Np , -LRB- u , v -RRB- \ in Ep \ Rightarrow -LRB- f -LRB- u -RRB- , f -LRB- v -RRB- -RRB- \ in Et $ . Note that the subgraph is not necessarily induced so that two pattern nodes that are not linked by an edge may be matched to target nodes which are linked by an edge .

Back to list