A Note on the Spanning Subgraph Isomorphism Problem

• Item type: SIG Technical Reports(1)
• 公開日: 2016-11-17
• タイトル: A Note on the Spanning Subgraph Isomorphism Problem
• タイトル / 言語: en
• タイトル: A Note on the Spanning Subgraph Isomorphism Problem
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Department of Information and Communications Engineering Tokyo Institute of Technology
• 著者所属: Department of Information and Communications Engineering Tokyo Institute of Technology
• 著者所属: Department of Information and Communications Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information and Communications Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information and Communications Engineering Tokyo Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Information and Communications Engineering Tokyo Institute of Technology
• 著者名: Kenji, Ichikawa; Satoshi, Tayu; Shuichi, Ueno
• 著者名(英): Kenji, Ichikawa; Satoshi, Tayu; Shuichi, Ueno
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: We consider the subgraph isomorphism problem of two graphs which is to decide if a pattern graph is isomorphic to a subgraph of a base graph. It is known that the problem is NP - complete if the pattern and base graphs are bipartite permutation graphs with the same number of vertices. We show that the problem is NP - complete even if the pattern graph is an n - vertex tree of pathwidth at most 2 and the base graph is an n - vertex bipartite permutation graph.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We consider the subgraph isomorphism problem of two graphs which is to decide if a pattern graph is isomorphic to a subgraph of a base graph. It is known that the problem is NP - complete if the pattern and base graphs are bipartite permutation graphs with the same number of vertices. We show that the problem is NP - complete even if the pattern graph is an n - vertex tree of pathwidth at most 2 and the base graph is an n - vertex bipartite permutation graph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2016-AL-160, 号 15, p. 1-6, 発行日 2016-11-17
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会