抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
細粒縮小は,最短サイクル,全ペア最短経路(APSP),Radius,置換経路,第2最短経路など,nノード加重グラフ上のO(n ̄3)-時間アルゴリズムによる多くのコア問題の間の等価性を確立した。また,これらの問題は,mエッジnノード加重グラフに関するO(mn)時間アルゴリズムを持ち,そのようなアルゴリズムはより広い適応性を持っている。これらのmn限界はm≪n ̄2のとき最適であった。エッジ加重グラフにおける最小重量(2l+1)-クリーク問題は,n ̄2l+1-o(1)時間を必要とするという仮説から始めて,著者らは,形式m=Θ(n ̄1+1/l)の全てのスパース性に対して,有向加重グラフにおける最小重み(2l+1),有向加重グラフにおける最小重みづけグラフ,有向または無向加重グラフにおける最小重み(2l+1),有向または無向加重グラフにおける最短サイクル,有向加重グラフにおける,有向または非有向加重グラフにおける最短サイクル,有向加重グラフにおける2番目の最短経路,有向加重グラフにおける2次最短経路,有向加重グラフにおける与えられたノード間の2次最短経路,有向加重グラフにおけるP_p,有向または無向加重グラフにおけるP_p,有向加重グラフのWiener指数,有向加重グラフにおけるP_p,有向または無向加重グラフにおけるA_SP,有向加重グラフにおける最短サイクル,有向加重グラフにおけるP_p,および有向加重グラフにおける最すなわち,高密度グラフ問題の硬度から様々なスパースグラフ問題に対する硬度を証明した。また,著者らの結果は,kサイクル,最短サイクル,Radius,Wiener指数,およびAPSPを含む,非加重スパースグラフ問題に対するいくつかの関連仮説から,新しい条件付き下限を導いた。【JST・京大機械翻訳】
