This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License
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.
| Property | Value |
|---|---|
| dbo:abstract |
|
| dbo:wikiPageID |
|
| dbo:wikiPageLength |
|
| dbo:wikiPageRevisionID |
|
| dbo:wikiPageWikiLink |
|
| dbp:wikiPageUsesTemplate | |
| dcterms:subject | |
| rdfs:comment |
|
| rdfs:label |
|
| owl:sameAs | |
| prov:wasDerivedFrom | |
| foaf:isPrimaryTopicOf | |
| is dbo:wikiPageRedirects of | |
| is dbo:wikiPageWikiLink of | |
| is foaf:primaryTopic of |