論文の概要: Reconfiguring Shortest Paths in Graphs
- arxiv url: http://arxiv.org/abs/2112.07499v1
- Date: Tue, 14 Dec 2021 16:04:27 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-15 20:08:05.614854
- Title: Reconfiguring Shortest Paths in Graphs
- Title（参考訳）: グラフにおける最短パスの再構成
- Authors: Kshitij Gajjar, Agastya Vibhuti Jha, Manish Kumar and Abhiruk Lahiri
- Abstract要約: グラフ内の2つの最短パスを再構成することは、もう1つの最短パスを変更することを意味する。
問題を緩和した変種であっても、(a) は難解であることを示す。
また、この問題を最短経路上の連続頂点が一度に変更できる場合に限って、少なくとも$k$の問題を一般化する。
- 参考スコア（独自算出の注目度）: 0.8041901269397144
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Reconfiguring two shortest paths in a graph means modifying one shortest path
to the other by changing one vertex at a time so that all the intermediate
paths are also shortest paths. This problem has several natural applications,
namely: (a) revamping road networks, (b) rerouting data packets in synchronous
multiprocessing setting, (c) the shipping container stowage problem, and (d)
the train marshalling problem.
When modelled as graph problems, (a) is the most general case while (b), (c)
and (d) are restrictions to different graph classes. We show that (a) is
intractable, even for relaxed variants of the problem. For (b), (c) and (d), we
present efficient algorithms to solve the respective problems. We also
generalize the problem to when at most $k$ (for a fixed integer $k\geq 2$)
contiguous vertices on a shortest path can be changed at a time.
- Abstract（参考訳）: グラフ内の2つの最短経路を再構成することは、すべての中間経路が最短経路であるように、一度に1つの頂点を変更することによって、もう1つの最短経路を変更することを意味する。
この問題にはいくつかの自然応用がある。
(a)道路網の整備。
(b)同期マルチプロセッシング設定におけるデータパケットの再ルーティング
(c)運送容器詰まりの問題、及び
(d)列車のマーシャリングの問題。
グラフ問題としてモデル化された場合
a)が最も一般的な場合
(b)
(c)および
(d) は異なるグラフクラスに対する制限である。
私たちはそれを示します
(a)問題を緩和した変種であっても難解である。
のために
(b)
(c)および
(d)各問題を解決するための効率的なアルゴリズムを提案する。
また、この問題を少なくとも$k$(固定整数 $k\geq 2$) の最小経路上の連続頂点を一度に変更することができるように一般化する。
関連論文リスト
- Advances in quantum algorithms for the shortest path problem [0.18416014644193066]
我々は、構造化インスタンスの問題を解くために、隣接リストモデルに2つの有界エラー量子アルゴリズムを与える。
最初のアプローチは、量子フロー状態をサンプリングし、より小さな問題に対して古典的なアルゴリズムを実行することによって、元のグラフをスパース化することに基づいている。
2つ目のアプローチは、$tildeO(lsqrtm)$ stepsで最も短いパスを出力する分割および征服手順に基づいている。
論文 参考訳（メタデータ） (2024-08-19T21:30:02Z) - The Power of Graph Sparsification in the Continual Release Model [48.65946341463292]
本研究では,非プライベートなストリーミングアルゴリズムと静的グラフアルゴリズムによるスペーシング手法を新たに活用する。
エッジ微分プライベートアルゴリズムは、グラフ内のエッジの数に関して、サブ線形空間を使用する。
完全動的設定において、エッジプライバシーに対する加算誤差の低い境界を結論付ける。
論文 参考訳（メタデータ） (2024-07-24T20:15:07Z) - Exponential speedup of quantum algorithms for the pathfinding problem [5.260626311429307]
非重みのないグラフで$s, t$が与えられたとき、パスフィンディング問題の目標は、$s$-$t$パスを見つけることである。
溶接木に基づいてグラフ$G$を構築し、隣接リスト oracle $O$ でパスフィニング問題を定義する。
古典的なアルゴリズムが確率の高い指数時間で$s$-$t$パスを見つけることはできないことを証明している。
論文 参考訳（メタデータ） (2023-07-24T02:50:34Z) - Learning Graph Search Heuristics [48.83557172525969]
本稿では,新しいニューラルネットワークと学習アルゴリズムであるPHIL(Path Heuristic with Imitation Learning)について述べる。
我々の関数は、ノード距離の推測に有用なグラフ埋め込みを学習し、グラフサイズに依存しない一定時間で実行し、テスト時にA*のようなアルゴリズムに容易に組み込むことができる。
実験の結果、PHILはベンチマークデータセットの最先端の手法と比較して平均58.5%の探索ノード数を削減している。
論文 参考訳（メタデータ） (2022-12-07T22:28:00Z) - A Generalization of the Shortest Path Problem to Graphs with Multiple
Edge-Cost Estimates [13.046825574678579]
グラフにおける最短経路問題は、AI理論と応用の基礎である。
本稿では,エッジウェイトを複数回(推定)計算できる重み付き有向グラフのフレームワークを提案する。
次に、一般化問題に対する2つの完全アルゴリズムを提示し、その有効性を実証的に示す。
論文 参考訳（メタデータ） (2022-08-22T22:07:27Z) - Multi-scale Wasserstein Shortest-path Graph Kernels for Graph Classification [24.041871640927738]
We propose a novel graph kernel called the Multi-scale Wasserstein Shortest-Path graph kernel (MWSP)。
MWSPは,ほとんどのデータセットで最先端の性能を実現する。
論文 参考訳（メタデータ） (2022-06-02T10:50:46Z) - GraphWalks: Efficient Shape Agnostic Geodesic Shortest Path Estimation [93.60478281489243]
3次元曲面上の測地線経路を近似する学習可能なネットワークを提案する。
提案手法は,最短経路の効率的な近似と測地距離推定を提供する。
論文 参考訳（メタデータ） (2022-05-30T16:22:53Z) - Shortest Paths in Graphs with Matrix-Valued Edges: Concepts, Algorithm
and Application to 3D Multi-Shape Analysis [69.08838724594584]
グラフ内の最短経路を見つけることは、コンピュータビジョンやグラフィックスにおける多くの問題に関係している。
本稿では,行列値のエッジを持つグラフにおいて,最短経路のグラフ理論を新たに導入する。
論文 参考訳（メタデータ） (2021-12-08T08:23:37Z) - Optimal network online change point localisation [73.93301212629231]
オンラインネットワーク変化点検出の問題点について検討する。
この設定では、独立したベルヌーイネットワークの集合が順次収集され、基礎となる変化点が生じる。
目的は、虚偽のアラームの数または確率の制約に応じて、それが存在する場合、変更点をできるだけ早く検出することです。
論文 参考訳（メタデータ） (2021-01-14T07:24:39Z) - Learning to Solve Combinatorial Optimization Problems on Real-World
Graphs in Linear Time [12.43303621344215]
専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。
本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。
最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
論文 参考訳（メタデータ） (2020-06-06T01:35:45Z) - Wasserstein-based Graph Alignment [56.84964475441094]
我々は,より小さいグラフのノードと大きなグラフのノードをマッチングすることを目的とした,1対多のグラフアライメント問題に対する新しい定式化を行った。
提案手法は,各タスクに対する最先端のアルゴリズムに対して,大幅な改善をもたらすことを示す。
論文 参考訳（メタデータ） (2020-03-12T22:31:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。