抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
著者らは,R3の点の有限集合を入力する多項式時間アルゴリズムを提案し,任意の精度,最大1の直径を持つ最大部分集合を計算した。より正確に,著者らは,ユニットボールグラフにおける最大クリークのために,最初のランダム化EPTASと決定論的PTASを与えた。著者らの近似アルゴリズムは,平面において任意の半径を有するディスクグラフに関しても研究した。約30年前に,エレガント多項式時間アルゴリズムが,単位ディスクグラフ[Clark,Colbourn,Johnson;離散Mathematics90]上の最大クリークに対して見出された。それ以来,それは,追跡可能性が一般的なディスクグラフに拡張できるかどうかにかかわらず,興味深い未解決の問題であった。最近,2つの奇数サイクルの分離結合は,ディスクグラフ[Bonnet,Gianopoulos,Kim,Rzazewski,Sikora;SOCG18]の補完ではないことが示された。これにより,筆者らは,ディスクグラフ上のMax Cliqueに対するQPTASとサブ指数アルゴリズムを導出することを可能にした。本論文では,ランダム化EPTAS(および決定論的PTAS)に対する近似性を改善した。より正確に,著者らは,誘導サブグラフ,有界VC次元,および線形独立数として,2つの奇数サイクルの分離結合を持たないグラフ上の独立数を計算するためのランダム化EPTASを得た。次に,より高い次元におけるディスクに対するMaxクリークを計算する問題に取り組んだ。ディスクグラフのようなユニットボールの交差グラフは,誘導されたサブグラフとして2つの奇数サイクルの補完を許容しないことを示した。これは,最初の結果と組み合わせて,単位球グラフ上のMax Cliqueに対するランダム化EPTASを直接的に与える。星コントラストにおいて,著者らは,ボールグラフとユニット4次元ディスクグラフに関して,MaxクリークがNP困難であり,指数関数時間においてさえ近似スキームを許容しないことを示した。Copyright 2019 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】
