WEKO3
アイテム
Graph Isomorphism Completeness for Trapezoid Graphs
http://hdl.handle.net/10258/00010880
http://hdl.handle.net/10258/00010880f3e8c565-8b62-4cbc-a964-d0cd5c98fbf2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
transfun_E98_A_1838 (248.1 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article.(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-06-06 | |||||||||||||
| 書誌情報 |
en : IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E98.A, 号 8, p. 1838-1840, 発行日 2015 |
|||||||||||||
| タイトル | ||||||||||||||
| タイトル | Graph Isomorphism Completeness for Trapezoid Graphs | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | comparability graphs | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | graph isomorphism | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | interval dimension | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | trapezoid graphs | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||||||||
| 資源タイプ | journal article | |||||||||||||
| アクセス権 | ||||||||||||||
| アクセス権 | open access | |||||||||||||
| アクセス権URI | http://purl.org/coar/access_right/c_abf2 | |||||||||||||
| 著者 |
髙岡, 旭
× 髙岡, 旭
|
|||||||||||||
| 室蘭工業大学研究者データベースへのリンク | ||||||||||||||
| 髙岡 旭（TAKAOKA Asahi） | ||||||||||||||
| http://rdsoran.muroran-it.ac.jp/html/200000242_ja.html | ||||||||||||||
| 抄録 | ||||||||||||||
| 内容記述タイプ | Abstract | |||||||||||||
| 内容記述 | The complexity of the graph isomorphism problem for trapezoid graphs has been open over a decade. This paper shows that the problem is GI-complete. More precisely, we show that the graph isomorphism problem is GI-complete for comparability graphs of partially ordered sets with interval dimension 2 and height 3. In contrast, the problem is known to be solvable in polynomial time for comparability graphs of partially ordered sets with interval dimension at most 2 and height at most 2. | |||||||||||||
| 言語 | en | |||||||||||||
| 出版者 | ||||||||||||||
| 出版者 | The Institute of Electronics, Information and Communication Engineers | |||||||||||||
| 言語 | en | |||||||||||||
| 出版者版へのリンク | ||||||||||||||
| 10.1587/transfun.E98.A.1838 | ||||||||||||||
| https://doi.org/10.1587/transfun.E98.A.1838 | ||||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | 10.1587/transfun.E98.A.1838 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0916-8508 | |||||||||||||
| 権利 | ||||||||||||||
| 言語 | en | |||||||||||||
| 権利情報 | Copyright(C)2015 IEICE | |||||||||||||
| 著者版フラグ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| フォーマット | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | application/pdf | |||||||||||||
