Difference between revisions of "Search for isomorphic subgraphs"
Jump to navigation
Jump to search
| [unchecked revision] | [quality revision] |
(Created page with "== Formulation of the problem == Let <math>G</math> and <math>H</math> be given graphs. '''Search for isomorphic subgraphs''' consists in finding out whether the graph <math>...") |
|||
| Line 19: | Line 19: | ||
[[Category:Articles in progress]] | [[Category:Articles in progress]] | ||
| + | |||
| + | [[Ru: Поиск изоморфных подграфов]] | ||
Revision as of 14:06, 10 February 2016
Contents
1 Formulation of the problem
Let [math]G[/math] and [math]H[/math] be given graphs. Search for isomorphic subgraphs consists in finding out whether the graph [math]G[/math] contains a subgraph isomorphic to [math]H[/math]. If the answer is positive, then it is required to produce at least one such subgraph.
2 Properties of the problem
The search for isomorphic subgraphs is an NP-complete problem. Consequently, none of the known algorithms solves this problem in polynomial time.
3 Algorithms for solving the problem
Ullman's algorithm[1][2] solves the problem of isomorphic subgraphs in exponential time; moreover,
- for a fixed graph [math]H[/math], the time is polynomial;
- for a planar graph [math]G[/math], the computation time is linear (if the graph [math]H[/math] is fixed).
Алгоритм VF2[3] is specially designed for working with large graphs.
4 References
- ↑ Ullmann, Julian R. “An Algorithm for Subgraph Isomorphism.” Journal of the ACM 23, no. 1 (January 1976): 31–42. doi:10.1145/321921.321925.
- ↑ Ullmann, Julian R. “Bit-Vector Algorithms for Binary Constraint Satisfaction and Subgraph Isomorphism.” Journal of Experimental Algorithmics 15 (March 2010): 1.1. doi:10.1145/1671970.1921702.
- ↑ Cordella, L P, P Foggia, C Sansone, and M Vento. “A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs.” IEEE Transactions on Pattern Analysis and Machine Intelligence 26, no. 10 (October 2004): 1367–72. doi:10.1109/TPAMI.2004.75.
