This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
Why does this page use a mixture of harvard and citation note [1] styles? 129.67.86.189 ( talk) 12:42, 26 April 2010 (UTC)
I'm surprised such a ubiquitously mentioned problem doesn't already have an algorithm outlined in pseudocode, or mention of an algorithm besides Ullmann's. Does another useful algorithm not even exist? Anyhow, I'm gonna tackle implementing this soon, and would love to post some pseudocode (or even a naive Java implementation) once I've completed it. If anyone knows of another algorithm for subgraph isomorphism, please don't hesitate to mention it (especially if it's simpler, and therefore more pseudocode-able, than Ullmann's.) -- Frizzil ( talk) 02:15, 17 October 2012 (UTC)
can anyone add a formal description of the problem? -- 141.53.216.143 ( talk) 10:40, 4 March 2013 (UTC)
The characterization of isomorphic in the formal statement of the problem is wrong I believe. The left-to-right implication should be a bi-implication. As it stands, the left-to-right implication is always true (take G_0 to be a graph with no edges). The right-to-left implication is what is important. So I suppose the implication could be reversed. I would not recommend it however. In the definition of the problem I feel it is best to give the most straightforward characterization, rather than one that relies on a (admittedly easy to see, for some at least) consequence of this specific problem - that any subgraph of G is an eligible candidate.
including survey papers thereof. 86.127.138.234 ( talk) 06:14, 18 February 2015 (UTC)
This may be a nitpick, but the proof only shows that subgraph isomorphism is NP-hard. To demonstrate NP-completeness, it has to also be shown to be in NP. While this is straightforward to do, by first checking that the function f is a bijection, and its domain is of size n, it should be mentioned.-- Houseofwealth ( talk) 19:40, 11 March 2020 (UTC)
This article is rated Start-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||||||||||||||||||||
|
Why does this page use a mixture of harvard and citation note [1] styles? 129.67.86.189 ( talk) 12:42, 26 April 2010 (UTC)
I'm surprised such a ubiquitously mentioned problem doesn't already have an algorithm outlined in pseudocode, or mention of an algorithm besides Ullmann's. Does another useful algorithm not even exist? Anyhow, I'm gonna tackle implementing this soon, and would love to post some pseudocode (or even a naive Java implementation) once I've completed it. If anyone knows of another algorithm for subgraph isomorphism, please don't hesitate to mention it (especially if it's simpler, and therefore more pseudocode-able, than Ullmann's.) -- Frizzil ( talk) 02:15, 17 October 2012 (UTC)
can anyone add a formal description of the problem? -- 141.53.216.143 ( talk) 10:40, 4 March 2013 (UTC)
The characterization of isomorphic in the formal statement of the problem is wrong I believe. The left-to-right implication should be a bi-implication. As it stands, the left-to-right implication is always true (take G_0 to be a graph with no edges). The right-to-left implication is what is important. So I suppose the implication could be reversed. I would not recommend it however. In the definition of the problem I feel it is best to give the most straightforward characterization, rather than one that relies on a (admittedly easy to see, for some at least) consequence of this specific problem - that any subgraph of G is an eligible candidate.
including survey papers thereof. 86.127.138.234 ( talk) 06:14, 18 February 2015 (UTC)
This may be a nitpick, but the proof only shows that subgraph isomorphism is NP-hard. To demonstrate NP-completeness, it has to also be shown to be in NP. While this is straightforward to do, by first checking that the function f is a bijection, and its domain is of size n, it should be mentioned.-- Houseofwealth ( talk) 19:40, 11 March 2020 (UTC)