WEKO3
アイテム
Min-orderableグラフの順序付き部分グラフ同型性判定問題
https://ipsj.ixsq.nii.ac.jp/records/241028
https://ipsj.ixsq.nii.ac.jp/records/241028f86ef367-d325-4e6a-85dd-c21f7f5a6baf
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL24200012.pdf (1.0 MB)
2026年11月19日からダウンロード可能です。
|
Copyright (c) 2024 by the Information Processing Society of Japan
|
|
| 非会員：¥660, IPSJ:学会員：¥330, AL:会員：¥0, DLIB:会員：¥0 | ||
| Item type | SIG Technical Reports(1) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2024-11-19 | |||||||||
| タイトル | ||||||||||
| タイトル | Min-orderableグラフの順序付き部分グラフ同型性判定問題 | |||||||||
| 言語 | ||||||||||
| 言語 | jpn | |||||||||
| 資源タイプ | ||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||
| 資源タイプ | technical report | |||||||||
| 著者所属 | ||||||||||
| 室蘭工業大学 | ||||||||||
| 著者所属 | ||||||||||
| 室蘭工業大学 | ||||||||||
| 著者名 |
佐藤, 景大
× 佐藤, 景大
× 高岡, 旭
|
|||||||||
| 論文抄録 | ||||||||||
| 内容記述タイプ | Other | |||||||||
| 内容記述 | 部分グラフ同型性判定問題とは，2 つのグラフ G と H が与えられたときに G が H と同型な部分グラフを含むかを判定する問題である．順序付き部分グラフ同型性判定問題は今村・大館・斎藤（2024）によって提案された問題であり，グラフそのものとともに頂点順序が与えられたときに順序を保ったまま頂点を割り当てる制限付きの部分グラフ同型性判定問題である．順序付き部分グラフ同型性判定問題に対しては入力のグラフが区間順序を持つ区間グラフであるときに多項式時間可解であることが知られている．一方，比較可能順序を持つ二部グラフ，完全消去順序を持つスプリットグラフ，補比較可能順序を持つ補二部グラフ上での順序付き部分グラフ同型性判定問題は NP 完全である．本論文では 2 方向直交半直線交差グラフ，adjusted interval digraphs，signed interval digraphs 上での順序付き部分グラフ同型性判定問題を解く多項式時間アルゴリズムを提案する．これらのグラフクラスは，区間グラフと共に，min ordering，または X-underbar property と呼ばれる共通の特徴づけを持つことが知られている．さらに，弦二部グラフと強弦グラフ上での順序付き部分グラフ同型性判定問題が NP 完全であることを示す． | |||||||||
| 書誌レコードID | ||||||||||
| 収録物識別子タイプ | NCID | |||||||||
| 収録物識別子 | AN1009593X | |||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2024-AL-200, 号 12, p. 1-8, 発行日 2024-11-19 |
|||||||||
| ISSN | ||||||||||
| 収録物識別子タイプ | ISSN | |||||||||
| 収録物識別子 | 2188-8566 | |||||||||
| Notice | ||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||
| 出版者 | ||||||||||
| 言語 | ja | |||||||||
| 出版者 | 情報処理学会 | |||||||||
