词条 | Maximum common edge subgraph |
释义 |
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
References1. ^{{citation | last1 = Bahiense | first1 = L. | last2 = Manic | first2 = G. | last3 = Piva | first3 = B. | last4 = de Souza | first4 = C. C. | doi = 10.1016/j.dam.2012.01.026 | issue = 18 | journal = Discrete Applied Mathematics | pages = 2523–2541 | title = The maximum common edge subgraph problem: A polyhedral investigation | volume = 160 | year = 2012}}. {{algorithm-stub}} 1 : Computational problems in graph theory |
随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。