| 大会名称 |
| 2016年 総合大会 |
| 大会コ－ド |
| 2016G |
| 開催年 |
|
2016
|
| 発行日 |
|
2016/3/1
|
| セッション番号 |
|
AS-1
|
| セッション名 |
|
グラフ理論の工学的魅力を語る － 基礎から最前線の応用まで
|
| 講演日 |
|
2016/3/17
|
| 講演場所(会議室等) |
|
総合学習プラザ 2F 第16講義室
|
| 講演番号 |
|
AS-1-5
|
| タイトル |
|
A Note on the Spanning Subgraph Isomorphism Problem
|
| 著者名 |
|
◎Kenji Ichikawa, Satoshi Tayu, Shuichi Ueno,
|
| キーワード |
|
Subgraph isomorphism problem, Bipartite permutation graph, NP-completeness
|
| 抄録 |
|
The subgraph isomorphism problem is to decide if a graph (called the pattern graph) is isomorphic to a subgraph of another graph (called the base graph). The problem is a generalization of the Hamiltonian path problem which is well-known to be NP-complete. And is NP-complete even for very restricted graph classes such as bipartite perumutation graphs. This paper shows that the subgraph isomorphism problem is NP-complete even if the pattern graph is an n-vertex tree and the base graph is an n-vertex bipartite permutation graph.
|
| 本文pdf |
|
PDF download
|
