文献

J-GLOBAL ID：202102224815724722   整理番号：21A2365422

区間順序上の最長増加部分列

著者 (4件)： 青池宥希 (横浜市大) ,  清見礼 (成蹊大) ,  小林靖明 (京大) ,  大舘陽太 (名古屋大)
資料名： 情報処理学会研究報告(Web)  (IPSJ Technical Report (Web))
巻： 2021  号： AL-184  ページ： Vol.2021-AL-184,No.8,1-3 (WEB ONLY)  発行年： 2021年08月18日 
JST資料番号： U0451A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 与えられたn個の数の列の最長増加部分列はペーシェンスソーティングを用いてO(n log n)時間で求められることが知られている。本発表では,最長増加部分列問題を区間順序上の問題に一般化し,ペーシェンスソーティングの自然な拡張によりO(n log n)時間の解法を与える。(著者抄録)

シソーラス用語： *数列 ,  部分 ,  有向グラフ ,  機械学習 ,  閉路 ,  木【グラフ】 ,  NP完全問題 ,  *計算量理論 ,  順序
準シソーラス用語： *最長増加部分列 ,  区間順序 ,  *DAG【グラフ】 ,  根つき木 ,  区間グラフ

分類 (2件)： 数値計算  (JE02000J) ,  計算理論  (JB02000A)

引用文献 (5件)：

• Adam L. Buchsbaum and Michael T. Goodrich. Three-dimensional layers of maxima. Algorithmica, Vol. 39, No. 4, pp. 275-286, 2004.
• J. M. Hammersley. A few seedlings of research. In Proceedings of the Sixth Berkeley Symposium on Mathematical Statistics and Probability (Univ. California, Berkeley, Calif., 1970/1971), Vol. I: Theory of statistics, pp. 345-394, 1972.
• Veli Mäkinen, Alexandru I. Tomescu, Anna Kuosmanen, Topi Paavilainen, Travis Gagie, and Rayan Chikhi. Sparse dynamic programming on dags with small width. ACM Trans. Algorithms, Vol. 15, No. 2, 2019.
• C. L. Mallows. Patience sorting. Vol. 4, No. 2, pp. 148-149, ???? 1962.
• Mihalis Yannakakis. The complexity of the partial order dimension problem. SIAM Journal on Algebraic Discrete Methods, Vol. 3, No. 3, pp. 351-358, 1982.

タイトルに関連する用語 (1件)： 順序