Maximum common edge subgraph: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 12:22, 27 November 2024

Given two graphs $G$ and $G'$ , the maximum common edge subgraph problem is the problem of finding a graph $H$ with as many edges as possible which is isomorphic to both a subgraph of $G$ and a subgraph of $G'$ .

The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph $H$ is isomorphic to a subgraph of another graph $G$ if and only if the maximum common edge subgraph of $G$ and $H$ has the same number of edges as $H$ . The problem is APX-hard, unless the two input graphs $G$ and $G'$ are required to have the same number of vertices.^[1]

References

^ Bahiense, L.; Manic, G.; Piva, B.; de Souza, C. C. (2012), "The maximum common edge subgraph problem: A polyhedral investigation", Discrete Applied Mathematics, 160 (18): 2523–2541, doi:10.1016/j.dam.2012.01.026.

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

This graph theory-related article is a stub. You can help Wikipedia by expanding it.

[1] Bahiense, L.; Manic, G.; Piva, B.; de Souza, C. C. (2012), "The maximum common edge subgraph problem: A polyhedral investigation", Discrete Applied Mathematics, 160 (18): 2523–2541, doi:10.1016/j.dam.2012.01.026.

[1]

@@ Line 1: / Line 1: @@
+{{one source |date=April 2024}}
-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 (discrete 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 as many  edges as possible which is [[graph isomorphism|isomorphic]] to both 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]]: a graph <math>H</math> is isomorphic to a subgraph of another graph <math>G</math> if and only if the maximum common edge subgraph of <math>G</math> and <math>H</math> has the same number of edges as <math>H</math>. The problem is [[APX-hard]], unless the two input graphs <math>G</math> and <math>G'</math> are required to have the same number of vertices.<ref>{{citation
+ | last1 = Bahiense | first1 = L.
+ | last2 = Manic | first2 = G.
+ | last3 = Piva | first3 = B.
+ | last4 = de Souza | first4 = C. C.
+ | doi = 10.1016/j.dam.2012.01.026
+ | issue = 18
+ | journal = Discrete Applied Mathematics
+ | pages = 2523–2541
+ | title = The maximum common edge subgraph problem: A polyhedral investigation
+ | volume = 160
+ | year = 2012| doi-access = free
+ }}.</ref>
 == See also ==
 *[[Maximum common subgraph isomorphism problem]]
 *[[Subgraph isomorphism problem]]
@@ Line 10: / Line 22: @@
 == References ==
+{{reflist}}
-<references />
 [[Category:Computational problems in graph theory]]
@@ Line 16: / Line 28: @@
 {{algorithm-stub}}
+{{graph-stub}}