文献

J-GLOBAL ID：202002214963168209   整理番号：20A0425890

角度被覆:アルゴリズムと複雑性【JST・京大機械翻訳】

Angle Covers: Algorithms and Complexity

著者 (4件)： Evans William (Department of Computer Science, University of British Columbia, Vancouver, B.C., Canada) ,  Gethner Ellen (Department of Computer Science and Engineering, University of Colorado, Denver, CO, U.S.A.) ,  Spalding-Jamieson Jack (Department of Computer Science, University of British Columbia, Vancouver, B.C., Canada) ,  Wolff Alexander (Universitaet Wuerzburg, Wuerzburg, Germany)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12049  ページ： 94-106  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 回転システムを持つグラフ,すなわち,あらゆる頂点に対して,入射エッジの円形秩序化を考慮した。このようなグラフを与えると,各エッジが少なくとも一つのペアに参加するように,角度が順序付けにおける一対の連続エッジに対して頂点ごとに写像される。著者らは,最大次数4の任意グラフが角度カバーを許容することを示し,次数3頂点を持たないグラフが角度カバーを有するかどうかを決定するための多時間アルゴリズムを与え,最大次数5のグラフを与えると,それが角度カバーを許容するかどうかを決定することが困難であることを証明した。また,各頂点が角度の固定数[数式:原文を参照]を選択するか,または角度が2つ以上の連続したエッジからなる角度カバー問題の拡張を考察した。平面グラフの2ブローアップが同形の厚さ2を持つかどうかを決定する問題に対する角度カバーの適用を示した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *被覆 ,  *アルゴリズム ,  平面グラフ
準シソーラス用語： 順序づけ ,  複雑性 , 【Automatic Indexing@JST】

分類 (3件)： 図形・画像処理一般  (JE04010I) ,  計算理論  (JB02000A) ,  パターン認識  (JE07000S)

タイトルに関連する用語 (2件)： アルゴリズム ,  複雑性