请输入您要查询的百科知识:

 

词条 Maximum common edge subgraph
释义

  1. See also

  2. References

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

1. ^{{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条英语、德语、日语等多语种百科知识,基本涵盖了大多数领域的百科知识,是一部内容自由、开放的电子版国际百科全书。

 

Copyright © 2023 OENC.NET All Rights Reserved
京ICP备2021023879号 更新时间:2024/11/14 0:04:11