WEKO3
アイテム
A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs
http://hdl.handle.net/10258/00010881
http://hdl.handle.net/10258/00010881bf4d6438-d2de-453d-ab32-45c013fc7cbf
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
transfun_2021DMP0001 (801.9 kB)
|
|
| Item type | 学術雑誌論文 / Journal Article.(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2023-06-06 | |||||||||||||
| 書誌情報 |
en : IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences 巻 E105.A, 号 9, p. 1223-1227, 発行日 2022 |
|||||||||||||
| タイトル | ||||||||||||||
| タイトル | A Note on the Intersection of Alternately Orientable Graphs and Cocomparability Graphs | |||||||||||||
| 言語 | en | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | eng | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | alternately orientable graphs | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | cocomparability graphs | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | recognition problem | |||||||||||||
| キーワード | ||||||||||||||
| 言語 | en | |||||||||||||
| 主題Scheme | Other | |||||||||||||
| 主題 | simple-triangle 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 | |||||||||||||
| 内容記述 | We studied whether a statement similar to the Ghouila-Houri's theorem might hold for alternating orientations of cocomparability graphs. In this paper, we give the negative answer. We prove that it is NP-complete to decide whether a cocomparability graph has an orientation that is alternating and acyclic. Hence, cocomparability graphs with an acyclic alternating orientation form a proper subclass of alternately orientable cocomparability graphs. We also provide a separating example, that is, an alternately orientable cocomparability graph such that no alternating orientation is acyclic. | |||||||||||||
| 言語 | en | |||||||||||||
| 出版者版へのリンク | ||||||||||||||
| 10.1587/transfun.2021DMP0001 | ||||||||||||||
| https://doi.org/10.1587/transfun.2021DMP0001 | ||||||||||||||
| DOI | ||||||||||||||
| 関連タイプ | isIdenticalTo | |||||||||||||
| 識別子タイプ | DOI | |||||||||||||
| 関連識別子 | 10.1587/transfun.2021DMP0001 | |||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | PISSN | |||||||||||||
| 収録物識別子 | 0916-8508 | |||||||||||||
| 権利 | ||||||||||||||
| 言語 | en | |||||||||||||
| 権利情報 | Copyright(C)2022 IEICE | |||||||||||||
| 著者版フラグ | ||||||||||||||
| 出版タイプ | VoR | |||||||||||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||||||||||
| フォーマット | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | application/pdf | |||||||||||||
