图 书 馆
结合非子图同构A Bound for Non-Subgraph Isomorphism |
|
| 课程网址: | http://videolectures.net/gbr07_schellewald_abfns/ |
| 主讲教师: | Christian Schellewald |
| 开课单位: | 都柏林城市大学 |
| 开课时间: | 2007-07-04 |
| 课程语种: | 英语 |
| 中文简介: |  |
| 课程简介: | In this paper we propose a new lower bound to a subgraph isomorphism problem. This bound can provide a proof that no subgraph isomorphism between two graphs can be found. The computation is based on the SDP relaxation of a – to the best of our knowledge – new combinatorial optimisation formulation for subgraph isomorphism. We consider problem instances where only the structures of the two graph instances are given and therefore we deal with simple graphs in the first place. The idea is based on the fact that a subgraph isomorphism for such problem instances always leads to 0 as lowest possible optimal objective value for our combinatorial optimisation problem formulation. Therefore, a lower bound that is larger than 0 represents a proof that a subgraph isomorphism don’t exist in the problem instance. But note that conversely, a negative lower bound does not imply that a subgraph isomorphism must be present and only indicates that a subgraph isomorphism is still possible. |
| 关 键 词: | 子图同构; SDP松弛; 组合优化 |
| 课程来源: | 视频讲座网 |
| 最后编审: | 2020-10-22：chenxin |
| 阅读次数: | 82 |