文献

J-GLOBAL ID：202002245550105542   整理番号：20A1035011

一般的な分岐とそれらの双対証明書【JST・京大機械翻訳】

Popular Branchings and Their Dual Certificates

著者 (5件)： Kavitha Telikepalli (TIFR, Mumbai, India) ,  Kiraly Tamas (Eotvos University, Budapest, Hungary) ,  Matuschke Jannik (KU Leuven, Leuven, Belgium) ,  Schlotter Ildiko (Budapest University of Technology and Economics, and KRTK KTI, Budapest, Hungary) ,  Schmidt-Kraepelin Ulrike (Technische Universitaet Berlin, Berlin, Germany)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12125  ページ： 223-237  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： Gは,あらゆるノードがその入っているエッジの上に選好を持つ有向グラフである。ノードの選好は,分岐,すなわち,指向された森林に対する選好に自然に拡張する;分岐Bは,Bが任意の分岐に対してヘッドからヘッドへの選択(ここでノードが投票する)を失わない場合には一般的である。このような人気のある分岐は,液体民demoにおける自然応用を有する。一般的な分岐問題は,Gがポピュラーな分岐を許容するか否かを決定することである。二重証明書の観点からポピュラーな分岐の特性化を行い,この特性化を用いて,一般的な分岐問題に対する効率的な組合せアルゴリズムを設計した。選好が弱いランク付けであるとき,オリジナル空間におけるポピュラーな分岐ポリトープを定式化するために著者らの特性化を使用し,また,著者らのアルゴリズムが,少なくとも非人気マージンを有する分岐を計算するために修正できることを示した。選好が厳しい場合には,「近似的に人気のある」分岐が常に存在することを示した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： アルゴリズム ,  *有向グラフ ,  近似法 ,  等級づけ ,  キャラクタリゼーション ,  定式化
準シソーラス用語： *証明書 ,  ポリトープ ,  組合せアルゴリズム , 【Automatic Indexing@JST】

分類 (2件)： 人工知能  (JE08000Z) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (2件)： 分岐 ,  証明書