Maximum common edge subgraph: Difference between revisions
Content deleted Content added
Singleheart (talk | contribs) update reference |
m WP:CHECKWIKI errors fixed + general fixes using AWB (8961) |
||
| Line 1: | Line 1: | ||
Given two [[graph (mathematics)|graph]]s <math>G</math> and <math>G'</math>, the '''maximum common edge subgraph problem''' is the problem of finding a graph <math>H</math> with a maximal number of edges which is [[graph isomorphism|isomorphic]] to a [[Glossary_of_graph_theory#Subgraphs|subgraph]] of <math>G</math> and a subgraph of <math>G'</math>. |
Given two [[graph (mathematics)|graph]]s <math>G</math> and <math>G'</math>, the '''maximum common edge subgraph problem''' is the problem of finding a graph <math>H</math> with a maximal number of edges which is [[graph isomorphism|isomorphic]] to a [[Glossary_of_graph_theory#Subgraphs|subgraph]] of <math>G</math> and a subgraph of <math>G'</math>. |
||
The maximum common edge subgraph problem on general graphs is [[NP-complete]] as it is a generalization of [[subgraph isomorphism]]. Unless <math>G</math> and <math>G'</math> are required to have the same number of vertices, the problem is [[APX-hard]]<ref>L. Bahiense, G. Manic, B. Piva, C.C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, 160(18):2523-2541, 2012. http://dx.doi.org/10.1016/j.dam.2012.01.026</ref> |
The maximum common edge subgraph problem on general graphs is [[NP-complete]] as it is a generalization of [[subgraph isomorphism]]. Unless <math>G</math> and <math>G'</math> are required to have the same number of vertices, the problem is [[APX-hard]].<ref>L. Bahiense, G. Manic, B. Piva, C.C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, 160(18):2523-2541, 2012. http://dx.doi.org/10.1016/j.dam.2012.01.026</ref> |
||
== See also == |
== See also == |
||
| Line 11: | Line 11: | ||
== References == |
== References == |
||
<references /> |
<references /> |
||
| ⚫ | |||
[[Category:Graph theory]] |
[[Category:Graph theory]] |
||
| ⚫ | |||
Revision as of 06:01, 8 March 2013
Given two graphs and , the maximum common edge subgraph problem is the problem of finding a graph with a maximal number of edges which is isomorphic to a subgraph of and a subgraph of .
The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism. Unless and are required to have the same number of vertices, the problem is APX-hard.[1]
See also
- Maximum common subgraph isomorphism problem
- Subgraph isomorphism problem
- Induced subgraph isomorphism problem
References
- ^ L. Bahiense, G. Manic, B. Piva, C.C. de Souza. The maximum common edge subgraph problem: A polyhedral investigation. Discrete Applied Mathematics, 160(18):2523-2541, 2012. http://dx.doi.org/10.1016/j.dam.2012.01.026
 | This computer science article is a stub. You can help Wikipedia by expanding it. |