Maximum Common Edge Subgraph (MCES)

From GM-RKB
Jump to navigation Jump to search

A Maximum Common Edge Subgraph (MCES) is a Maximum Common Subgraph that has as may edges as possible.



References

2018a

2018b

  • (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Maximum_common_edge_subgraph Retrieved:2018-11-25.
    • Given two graphs [math]\displaystyle{ G }[/math] and [math]\displaystyle{ G' }[/math], the maximum common edge subgraph problem is the problem of finding a graph [math]\displaystyle{ H }[/math] with as many edges as possible which is isomorphic to both a subgraph of [math]\displaystyle{ G }[/math] and a subgraph of [math]\displaystyle{ G' }[/math] .

      The maximum common edge subgraph problem on general graphs is NP-complete as it is a generalization of subgraph isomorphism: a graph [math]\displaystyle{ H }[/math] is isomorphic to a subgraph of another graph [math]\displaystyle{ G }[/math] if and only if the maximum common edge subgraph of [math]\displaystyle{ G }[/math] and [math]\displaystyle{ H }[/math] has the same number of edges as [math]\displaystyle{ H }[/math] . Unless the two inputs [math]\displaystyle{ G }[/math] and [math]\displaystyle{ G' }[/math] to the maximum common edge subgraph problem are required to have the same number of vertices, the problem is APX-hard [1].

  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.

2018c

2002