WEKO3
アイテム
区間順序上の最長増加部分列
https://ipsj.ixsq.nii.ac.jp/records/212247
https://ipsj.ixsq.nii.ac.jp/records/2122474e77bc30-af16-4ce6-9f22-79ef1429deb7
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-AL21184008.pdf (729.5 kB)
|
Copyright (c) 2021 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | SIG Technical Reports(1) | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 公開日 | 2021-08-18 | |||||||||||||
| タイトル | ||||||||||||||
| タイトル | 区間順序上の最長増加部分列 | |||||||||||||
| 言語 | ||||||||||||||
| 言語 | jpn | |||||||||||||
| 資源タイプ | ||||||||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_18gh | |||||||||||||
| 資源タイプ | technical report | |||||||||||||
| 著者所属 | ||||||||||||||
| 横浜市立大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 成蹊大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 京都大学 | ||||||||||||||
| 著者所属 | ||||||||||||||
| 名古屋大学 | ||||||||||||||
| 著者名 |
青池, 宥希
× 青池, 宥希
× 清見, 礼
× 小林, 靖明
× 大舘, 陽太
|
|||||||||||||
| 論文抄録 | ||||||||||||||
| 内容記述タイプ | Other | |||||||||||||
| 内容記述 | 与えられた n 個の数の列の最長増加部分列はペーシェンスソーティングを用いて O(n log n) 時間で求められることが知られている．本発表では，最長増加部分列問題を区間順序上の問題に一般化し，ペーシェンスソーティングの自然な拡張により O(n log n) 時間の解法を与える． | |||||||||||||
| 書誌レコードID | ||||||||||||||
| 収録物識別子タイプ | NCID | |||||||||||||
| 収録物識別子 | AN1009593X | |||||||||||||
| 書誌情報 |
研究報告アルゴリズム（AL） 巻 2021-AL-184, 号 8, p. 1-3, 発行日 2021-08-18 |
|||||||||||||
| ISSN | ||||||||||||||
| 収録物識別子タイプ | ISSN | |||||||||||||
| 収録物識別子 | 2188-8566 | |||||||||||||
| Notice | ||||||||||||||
| SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. | ||||||||||||||
| 出版者 | ||||||||||||||
| 言語 | ja | |||||||||||||
| 出版者 | 情報処理学会 | |||||||||||||
