Maximum common edge subgraph
From Wikipedia, the free encyclopedia
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 .
This article relies largely or entirely on a single source. (April 2024) |
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 . The problem is APX-hard, unless the two input graphs and are required to have the same number of vertices.[1]
See also
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.