Space-Efficient Algorithms for Longest Increasing Subsequence (Extended Abstract)

• Item type: SIG Technical Reports(1)
• 公開日: 2017-09-12
• タイトル: Space-Efficient Algorithms for Longest Increasing Subsequence (Extended Abstract)
• タイトル / 言語: en
• タイトル: Space-Efficient Algorithms for Longest Increasing Subsequence (Extended Abstract)
• 言語: eng
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: Yokohama City University
• 著者所属: Nagoya University
• 著者所属: Kumamoto University
• 著者所属: RWTH Aachen University
• 著者所属: The University of Electro-Communications
• 著者所属(英): en
• 著者所属(英): Yokohama City University
• 著者所属(英): en
• 著者所属(英): Nagoya University
• 著者所属(英): en
• 著者所属(英): Kumamoto University
• 著者所属(英): en
• 著者所属(英): RWTH Aachen University
• 著者所属(英): en
• 著者所属(英): The University of Electro-Communications
• 著者名: Masashi, Kiyomi; Hirotaka, Ono; Yota, Otachi; Pascal, Schweitzer; Jun, Tarui
• 著者名(英): Masashi, Kiyomi; Hirotaka, Ono; Yota, Otachi; Pascal, Schweitzer; Jun, Tarui
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: Let π be a permutation of {1,...,n}. For 1 ≦ i1 ＜ … ＜ il ≦ n, a subsequence π<i1,...,il> of π is the sequence <π (i1),...,π (il)>. A subsequence π<i1,...,il> is an increasing subsequence of π if π (i1) ＜ … ＜ π (il). In this extended abstract, we present space-efficient algorithms for finding a longest increasing subsequence of a given permutation. Using √n words of additional working space, our algorithm solves the problem in O (n 1.5 log 2 n) time. It runs in O (n1.5 log n) time when we need only the length of a longest increasing subsequence.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Let π be a permutation of {1,...,n}. For 1 ≦ i1 ＜ … ＜ il ≦ n, a subsequence π<i1,...,il> of π is the sequence <π (i1),...,π (il)>. A subsequence π<i1,...,il> is an increasing subsequence of π if π (i1) ＜ … ＜ π (il). In this extended abstract, we present space-efficient algorithms for finding a longest increasing subsequence of a given permutation. Using √n words of additional working space, our algorithm solves the problem in O (n 1.5 log 2 n) time. It runs in O (n1.5 log n) time when we need only the length of a longest increasing subsequence.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2017-AL-164, 号 2, p. 1-3, 発行日 2017-09-12
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会