Maximum common edge subgraph problem
Given two graphs and , the maximum common edge subgraph problem is the problem of finding a graph with as many edges as possible which is isomorphic to both 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: a graph is isomorphic to a subgraph of another graph if and only if the maximum common edge subgraph of and has the same number of edges as . Unless the two inputs and to the maximum common edge subgraph problem 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
- ↑ 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 article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.