文献

J-GLOBAL ID：202202287726232041   整理番号：22A1063702

次数の最小辞書次数による強連結配向【JST・京大機械翻訳】

Strongly Connected Orientation with Minimum Lexicographic Order of Indegrees

著者 (3件)： Zhou Hongyu (School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China) ,  Hou Xinmin (School of Mathematical Sciences, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China) ,  Hou Xinmin (CAS Key Laboratory of Wu Wen-Tsun Mathematics, University of Science and Technology of China, Hefei, Anhui 230026, P. R. China)
資料名： International Journal of Foundations of Computer Science  (International Journal of Foundations of Computer Science)
巻： 33  号： 2  ページ： 149-153  発行年： 2022年 
JST資料番号： W0409A  ISSN： 0129-0541  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： シンガポール (SGP)  言語： 英語 (EN)

抄録/ポイント： 単純な無向グラフGを与えられた場合,Gの方位は,Gのあらゆるエッジを割り当てることである。Borradaileらは, greedy欲なアルゴリズムSC-Path-Reversal(多項式時間)を与え,最大次数を最小化する強く接続された方向を見出し,SC-Path-Reversalは,同様に「辞書のオーダー」目的を「最小化する」目的に最適であると推測する。このノートでは,著者らは,予測に正の回答を与え,アルゴリズムSC-PATH-REVERSALが,次数の辞書的順序を最小化する強く接続された方向を見つけることを示した。Copyright 2022 World Scientific Publishing Company All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  有向グラフ ,  無向グラフ ,  方向 ,  *辞書
準シソーラス用語： 多項式時間 , 【Automatic Indexing@JST】

著者キーワード (3件)： 配向 ,  強連結有向グラフ ,  度合い

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

タイトルに関連する用語 (3件)： 次数 ,  辞書 ,  配向