Maximum common edge subgraph
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. |