Subgraph Isomorphism Search Task

From GM-RKB
(Redirected from Subgraph Matching Task)
Jump to navigation Jump to search

A Subgraph Isomorphism Search Task is a Search Task for determining whether the first of two undirected graphs contains a subgraph that is isomorphic to the second one.



References

2020

  1. The original paper that proves the Cook–Levin theorem already showed subgraph isomorphism to be NP-complete, using a reduction from 3-SAT involving cliques.
  2. (1999); Nedetril & Ossona de Mendez (2012)

2019

2018

2016

2013a

2013b

2012

2011

2010

2008

2004a

2004b

1999

1976