抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフ交差番号は,広い測距応用を有する基本的で広範囲に研究された問題である。本問題では,そのエッジの画像間の交差数を最小化するために,平面に入力グラフGを描画することである。問題は,あまり困難であり,大規模な作業にもかかわらず,非自明な近似アルゴリズムは,有界度グラフのためにのみ知られている。この特別な場合でさえ,最良の電流アルゴリズムは,O(√n)近似を達成し,一方,最良の電流負結果は,一定因子近似を除外しなかった。問題のためのすべての現在の近似アルゴリズムは,同じパラダイム上に構築され,それはまた,G→εE’が平面であるようなエッジのセットE’(平面化セットと呼ばれる)を計算する。G≡E’の平面描画を計算した。次に,E’のエッジの延伸を結果として引き出す。残念なことに,グラフGの例があり,その中で,この方法の実装は,OPTが最適解の値であるΩ(OPT2)交差を発生しなければならない。この障壁は,この問題に対する近似アルゴリズムを設計する唯一の現在知られている手法と,O(√n)近似よりも良い降伏からそれを防止するように思える。本論文では,この障壁を克服することができる新しいパラダイムを提案した。有界次数グラフGとエッジの平面化E集合を与えるアルゴリズムを示し,|E′′|が相対的に小さいように,E’||E′′で他の平面化エッジ集合E′′を計算し,交差部における関与のエッジのない近最適描画が存在する。これにより,交差数問題の交差番号問題を,交差番号問題の変種に縮小することを可能にし,そこでは,各頂点に入射するエッジの規則化を入力の一部として固定する。この縮小では,元のグラフの交差数によって大まかに有界であるこの問題の例を得た。この新問題に対するランダム化アルゴリズムを示し,いくつかの定数に対して有界度グラフ上のグラフ交差番号に対する近似を得ることを可能にした。Copyright 2021 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
