Induced minor free graphs: Isomorphism and clique-width

• Item type: SIG Technical Reports(1)
• 公開日: 2015-06-05
• タイトル: Induced minor free graphs: Isomorphism and clique-width
• タイトル / 言語: en
• タイトル: Induced minor free graphs: Isomorphism and clique-width
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Kyoto University
• 著者所属: JAIST
• 著者所属: RWTH Aachen University
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): JAIST
• 著者所属(英): en
• 著者所属(英): RWTH Aachen University
• 著者名: Remy, Belmonte; Yota, Otachi; Pascal, Schweitzer
• 著者名(英): Remy, Belmonte; Yota, Otachi; Pascal, Schweitzer
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Given two graphs G and H, we say that G contains H as an induced minor a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is isomorphism complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. Those two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor or subgraph.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Given two graphs G and H, we say that G contains H as an induced minor a graph isomorphic to H can be obtained from G by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph H that Graph Isomorphism is polynomial-time solvable on H-induced-minor-free graphs or that it is isomorphism complete. Additionally, we classify those graphs H for which H-induced-minor-free graphs have bounded clique-width. Those two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor or subgraph.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2015-AL-153, 号 12, p. 1-6, 発行日 2015-06-05
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会