抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ここでは,現在,O(mn)時間アルゴリズムを持つスパースグラフ問題の細粒複雑性を考察し,そこでは,mはエッジ数であり,nは入力グラフにおける頂点の数である。このクラスは,APSP,MWC(最小重みサイクル),Radius,Eccentricity,BC(Beinterness Centerity)などを含む有向および無向グラフの両方に関するいくつかの重要な経路問題を含んでいる。グラフのスパース性を保存するスパース縮小の概念を導入し,O(mn)クラスにおけるグラフ問題の様々なペア間の線形時間スパース低減を示した。O(mn)クラスにおけるグラフ問題の間には多くのサブキュービック減少があるが,驚くほど,これらの保存スパース性は少ない。有向の場合,著者らの結果は,O(mn)クラス(いくつかの等価性を持つ)における問題の大きな収集に部分的順序を与え,多くの削減は非常に自明でない。非指向の場合では,MWCからAPSPへの2つの非自明なスパース低減と,非加重ANSC(すべてのノード最短サイクル)から非加重APSPへ与えた。有向グラフにおけるこれらのスパース低減のための新しい「ビットサンプリング法を開発して,それはまた,無向グラフにおけるサイクル発見問題のための改良またはより単純なアルゴリズムをもたらした。MWC硬度の概念を定式化し,それは有向グラフにおける最小重みサイクルがmnよりも多項式的に小さい時間において計算できないという仮定に基づいている。O(mn)クラスにおける有向経路問題に対するスパース低減は,2-SiSP(第2単純最短経路),s-t置換経路,Radius,Eccentricity,およびBCを含むこのクラスにおけるいくつかの問題がMWCハードであることを確立した。著者らの疎な低減は,2次クラスに対する3SUM硬度に類似したO(mn)クラスに対するMWC硬度を与え,これは,半世紀以上にわたってO(mn)時間を維持していた基本的でよく研究されたグラフ問題の大きな収集のためのサブmn硬度を示す。また,SETHが強力な指数時間仮説であり,k-DSHがnkよりも多項式的に小さい時間において計算できないという仮説である,同時にMWC-ハード,SETH-ハードおよびk-DSH-ハードであるO(mn)クラスにおける重要問題としてEccentricityおよびBCを同定した。スパース低減を用いたフレームワークは実世界グラフと非常に関連があり,スパースであり,O(mn)時間アルゴリズムが実際に使用されるものであり,O(n3)時間アルゴリズムではない。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】
