文献

J-GLOBAL ID：202102226500741342   整理番号：21A3306386

線形時間における木の最小射影線形化【JST・京大機械翻訳】

Minimum projective linearizations of trees in linear time

著者 (3件)： Alemany-Puig Lluis (Complexity and Quantitative Linguistics Lab, LARCA Research Group, Computer Science Department, Universitat Politecnica de Catalunya, Jordi Girona 1-3, 08034, Barcelona, Spain) ,  Esteban Juan Luis (Computer Science Department, Universitat Politecnica de Catalunya, Jordi Girona 1-3, 08034, Barcelona, Spain) ,  Ferrer-i-Cancho Ramon (Complexity and Quantitative Linguistics Lab, LARCA Research Group, Computer Science Department, Universitat Politecnica de Catalunya, Jordi Girona 1-3, 08034, Barcelona, Spain)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 174  ページ： Null  発行年： 2022年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 最小線形配置問題(MLA)は,グラフの頂点からπ*_u,v→π*|(u)-π(v)|を最小化する異なる整数までのマッピングπの発見から成る。その設定において,頂点は水平線上にあることがしばしば仮定され,エッジは上記の線上の半円として引き出される。木では,n=|V|における多項式時間での問題を解くために様々なアルゴリズムが利用可能である。配列が制約されるMLAのバリアントが存在する。Iordanskii,およびHochbergとStallmann(HS)は,配列が平面に制約されたとき(また,1ページの書籍埋め込みとしても知られる),O(n)-時間アルゴリズムを提唱した。また,投影(根がエッジで覆われていない平面埋込み)に制約される根付き樹木の線形配置を考察した。GildeaとTemperley(GT)は,それらがO(n)で実行を主張する射影配置のためのアルゴリズムをスケッチしたが,そのコストの正当化は与えなかった。対照的に,ParkとLevyは,GTのアルゴリズムがD_maxが最大度であるが,十分な詳細を提供しないO(nlog d_max)で動作することを主張した。ここでは,平面ケースに対するHSのアルゴリズムの誤差を修正し,投影ケースとのその関係を示し,O(n)時間において疑いなく走る投影および平面ケースに対する簡単なアルゴリズムを導いた。Copyright 2021 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  配置問題 ,  線形性 ,  *射影
準シソーラス用語： 多項式時間 ,  線形化 , 【Automatic Indexing@JST】

著者キーワード (5件)： アルゴリズム ,  最小線形配置問題 ,  射影性 ,  平面性 ,  ワンページ埋込み

分類 (2件)： グラフ理論基礎  (IA02020S) ,  計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 線形 ,  木 ,  射影 ,  線形化