論文の概要: Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach

• arxiv url: http://arxiv.org/abs/2509.05129v1
• Date: Fri, 05 Sep 2025 14:14:36 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-08 14:27:25.608668
• Title: Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
• Title（参考訳）: 小面積グラフ上でのエクサクタンス距離の効率的な計算法 -ラベリングアプローチ-
• Authors: Meihao Liao, Yueyang Pan, Rong-Hua Li, Guoren Wang,
• Abstract要約: 最短パス距離計算は、小木幅グラフ上で顕著な効率を達成する。 本手法では, 抵抗距離ラベルを$O(n cdot h_mathcalG)$ in $O(n cdot h_mathcalG2 cdot d_max$ とする。 我々のラベリングは、$O(h_mathcalG)$時間における正確なシングルペアクエリと$O(n cdot h_mathにおけるシングルソースクエリをサポートします。
• 参考スコア（独自算出の注目度）: 37.498311835613045
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficiency on small-treewidth graphs (e.g., road networks). In contrast, shortest-path distance computation achieves remarkable efficiency on such graphs by leveraging cut properties and tree decompositions. Motivated by this disparity, we first analyze the cut property of resistance distance. While a direct generalization proves impractical due to costly matrix operations, we overcome this limitation by integrating tree decompositions, revealing that the resistance distance $r(s,t)$ depends only on labels along the paths from $s$ and $t$ to the root of the decomposition. This insight enables compact labelling structures. Based on this, we propose \treeindex, a novel index method that constructs a resistance distance labelling of size $O(n \cdot h_{\mathcal{G}})$ in $O(n \cdot h_{\mathcal{G}}^2 \cdot d_{\max})$ time, where $h_{\mathcal{G}}$ (tree height) and $d_{\max}$ (maximum degree) behave as small constants in many real-world small-treewidth graphs (e.g., road networks). Our labelling supports exact single-pair queries in $O(h_{\mathcal{G}})$ time and single-source queries in $O(n \cdot h_{\mathcal{G}})$ time. Extensive experiments show that TreeIndex substantially outperforms state-of-the-art approaches. For instance, on the full USA road network, it constructs a $405$ GB labelling in $7$ hours (single-threaded) and answers exact single-pair queries in $10^{-3}$ seconds and single-source queries in $190$ seconds--the first exact method scalable to such large graphs.
• Abstract（参考訳）: 抵抗距離計算はグラフ解析の基本的な問題であるが、既存のランダムウォーク法は近似解に限られており、小さな木幅グラフ(例えば道路網)では効率が悪い。 対照的に、最短パス距離計算は、切断特性と木分解を利用して、そのようなグラフ上で顕著な効率を達成する。 この差に触発され、まず抵抗距離の切断特性を解析する。 直接一般化はコストのかかる行列演算により非現実的であるが、木分解を統合することでこの制限を克服し、抵抗距離$r(s,t)$が分解の根への$s$と$t$の経路に沿ったラベルにのみ依存することを明らかにする。 この洞察はコンパクトなラベリング構造を可能にする。 これに基づいて、$O(n \cdot h_{\mathcal{G}})$ in $O(n \cdot h_{\mathcal{G}}^2 \cdot d_{\max})$time, where $h_{\mathcal{G}}$ (ツリー高さ)および$d_{\max}$ (最大度)は、多くの実世界の小さなツリー幅グラフ(例えば道路ネットワーク)の小さな定数として振る舞う。 我々のラベリングは、$O(h_{\mathcal{G}})$時間での正確なシングルペアクエリと$O(n \cdot h_{\mathcal{G}})$時間でのシングルソースクエリをサポートします。 大規模な実験によると、TreeIndexは最先端のアプローチを大幅に上回っている。 例えば、USAのフルロードネットワークでは、時間7ドル(シングルスレッド)で405ドル(約4万5000円)のラベリングを構築し、正確なシングルペアクエリを秒10^{-3}で、単一のソースクエリを秒90ドル(約1万2000円)で答えます。

関連論文リスト

• Efficiently Constructing Sparse Navigable Graphs [11.317292211864013]
  我々は任意の距離関数の下で$O(log n)$-approximate sparsest navigable graphを構築するための$tildeO(n2)$ timeアルゴリズムを提案する。 また、本手法は、$alpha$-shortcut reachable と $tau$-monotonic graph を構築する際に、密接に関連し、実質的に重要な問題に対して立方体時間を超えることができることを示す。
  論文  参考訳（メタデータ） (2025-07-17T17:04:18Z)
• Graph Inference with Effective Resistance Queries [2.2349172369559156]
  一対の頂点間の有効抵抗(ER)を返すオラクルを用いてグラフ推論を研究する。 ERクエリから$n$-vertexグラフを一意に再構築できることは知られているが、他にはほとんど知られていない。
  論文  参考訳（メタデータ） (2025-02-25T16:37:25Z)
• Graph Unfolding and Sampling for Transitory Video Summarization via Gershgorin Disc Alignment [48.137527345353625]
  携帯電話からYouTubeやTikTokなどのソーシャルメディアサイトにアップロードされたユーザー生成ビデオ(UGV)は、短くて繰り返しではない。 我々は、ガーシュゴリンディスクアライメント(GDA)に基づく高速グラフサンプリングにより、遷移UGVを複数のディスクに線形時間で要約する。 提案アルゴリズムは,最先端の手法と比較して,映像の要約性能が向上し,複雑さが大幅に低減されていることを示す。
  論文  参考訳（メタデータ） (2024-08-03T20:08:02Z)
• Exact Algorithms and Lowerbounds for Multiagent Pathfinding: Power of Treelike Topology [0.0]
  我々は、与えられたグラフの$G上の一組の$kエージェントの経路を効率的に見つけることに重点を置いており、各エージェントはそのソースからターゲットへの経路を求める。 解の質の重要な尺度は提案されたスケジュールの長さ$ell$、すなわち最長経路の長さである。 MAPFは$G$+$ell$に対してW[1]ハードであり、FPTは$G$+$ell$であることを示す。
  論文  参考訳（メタデータ） (2023-12-15T09:42:46Z)
• Dynamic algorithms for k-center on graphs [3.568439282784197]
  エッジ更新を行う動的グラフ上での$k$-center問題に対する最初の効率的なアルゴリズムを提供する。 完全に動的な$(2+epsilon)$-approximationアルゴリズムを$k$-center問題に対して提案する。
  論文  参考訳（メタデータ） (2023-07-28T13:50:57Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  期待帯域幅$n tau$とエッジ密度$p$をエルドホス=R'enyiグラフ$G(n,q)$に植え込むモデルを考える。 低次アルゴリズムのクラスにおいて、関連する検出および回復問題に対する計算しきい値を特徴付ける。
  論文  参考訳（メタデータ） (2023-02-13T22:51:07Z)
• Fast Graph Sampling for Short Video Summarization using Gershgorin Disc Alignment [52.577757919003844]
  高速グラフサンプリングの最近の進歩を利用して,短い動画を複数の段落に効率よく要約する問題について検討する。 実験結果から,本アルゴリズムは最先端の手法と同等の映像要約を実現し,複雑さを大幅に低減した。
  論文  参考訳（メタデータ） (2021-10-21T18:43:00Z)
• Random Subgraph Detection Using Queries [29.192695995340653]
  植込み高密度部分グラフ検出問題は、与えられた(ランダム)グラフに異常に密度の高い部分グラフが存在するかどうかをテストするタスクを指す。 本稿では,適応的なエッジクエリを用いてグラフの比較的小さな部分のみを観測できる,上記の問題の自然な変形について考察する。 このモデルでは,植込み部分グラフの存在を検出するのに必要なクエリ数と十分なクエリ数(準多項式最適アルゴリズムを伴う)を決定する。
  論文  参考訳（メタデータ） (2021-10-02T07:41:17Z)
• Approximating the Log-Partition Function [16.59989033959959]
  基礎となるグラフ構造の性質を通じて近似比を定量化する手法を提案する。 グラフの有効抵抗を最小に抑えた平方根の逆に等しい近似比を実現するニアリニアタイム変量を提供する。
  論文  参考訳（メタデータ） (2021-02-19T22:57:32Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。