抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
直接Steinerネットワーク(DSN)問題は,k需要ペアの有向エッジ加重グラフG=(V,E)と集合D⊆V×Vの入力である。目的は,各(s,t)∈Dに対するs→t経路が存在する最も安価なネットワークN⊆Gを計算することである。この問題は,k[Dinur&Manrangsi,ITCS 2018]によるランタイムをパラメータ化する場合でも,Gap-ETHの下でk ̄1/4-o(1)近似アルゴリズムが存在しないので,あまり困難であることが知られている。これを考慮して,DSNのいくつかの特殊事例を系統的に研究し,パラメータkに対するパラメータ化近似性を決定した。bi-DSN_Planar問題に対して,目的は,コストが二方向グラフGにおける最適平面解の殆どである解N⊆Gを計算することであり,すなわち,Gのあらゆるエッジuvに対して,逆エッジvuが存在し,同じ重みを持つ。この問題は,いくつかのよく研究された特殊ケースの一般化である。著者らの主な結果は,この問題がkに対するパラメータ化近似方式(PAS)を許容することである。また,著者らの結果が,(a)著者らのPASの実行時間が有意に改善できないという意味で,また,(b)FPT=W[1]がなければ,PASがbi-DSN_Planarの任意の一般化に対して存在する可能性も証明する。DSNの1つの重要な特殊ケースは,強く接続されたSteiner部分グラフ(SCSS)問題であり,そのために,解ネットワークN⊆Gは,与えられたk端末集合を強く接続する必要がある。SCSSでは,k[Chitnisら,IPEC2013]によってパラメータ化された場合,パラメータ化された2近似が存在する前に観察された。著者らは,kのパラメータ化(2-ε)近似アルゴリズムがGap-ETHの下で存在しないことを示すことによって,著者らは,緊密な近似性結果を与えた。さらに,SCSSの双方向グラフへの入力を制限するとき,問題はNP困難であるが,kに対してはFPTになることを示す。【JST・京大機械翻訳】
