文献

J-GLOBAL ID：201702225286020751   整理番号：17A1185885

対数リストとその応用転位、逆転とブロック交換によるソーティング【Powered by NICT】

log-Lists and their applications to sorting by transpositions, reversals and block-interchanges

著者 (1件)： Rusu Irena (L.I.N.A., UMR 6241, Universite de Nantes, 2 rue de la Houssinire, BP 92208, 44322 Nantes, France)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 660  ページ： 1-15  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： リンクカット木は,D.D.により導入されているSleatorとR.E.カットとリンク操作下での頂点分離動的根付きツリーの森林を維持する効率的に目的とTarjan。これらの操作は,それぞれ木の中から部分木を分離,縁を利用した二樹木に連結している。,リンク・カット・ツリーはツリーのルートを変化させると樹木のアーク上で定義されたコスト値に数更新と質問を実行できるようにする。これらすべての演算がO(logn)償却または最悪ケース時間で行い,実施に依存して,nは森林の全サイズである。本論文では,リンク切断木(,logリストと呼ぶ)を用いて実装された元素のリストをリストに古典的な操作だけでなく,リストに線形時間を要する通常いくつかの他の必須作業のためのO(logn)の一般的な実行時間を得ることができることを示した。このような作業は,そのエンドポイントにより定義されたsublist,リスト中で与えられた元素の位置あるいはリストに与えられた位置に置かれた要素における最小/最大要素を見つけることが必要とされるまたはそれらが価値を付加a,または 1sublistにおける全ての元素による増殖に必要である。さらに,転位および/または反転および/またはブロック交換による順列ソーティングのためのいくつかの既存のアルゴリズムを実装し,それらの全てのためのO(n logn)実行時間を得るためにlogリストを用いた。このようにして,いくつかのアルゴリズムの実行時間が改善され,一方他の場合にこのアルゴリズムが最良の既存の実装と同様に行った。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： アーク放電 ,  *対数 ,  順列 ,  *ソーティング ,  線形性 ,  アルゴリズム
準シソーラス用語： 実行時間 ,  部分木 , 【Automatic Indexing@JST】

著者キーワード (4件)： 動的リストランキング ,  順列ソーティング ,  リンクカットツリー ,  二重リンク付きリスト

分類 (2件)： 計算理論  (JB02000A) ,  人工知能  (JE08000Z)

タイトルに関連する用語 (6件)： 対数 ,  リスト ,  応用 ,  転位 ,  逆転 ,  ソーティング