論文の概要: Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
- arxiv url: http://arxiv.org/abs/2605.13402v1
- Date: Wed, 13 May 2026 11:57:35 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-14 23:30:28.026926
- Title: Fast and Compact Graph Cuts for the Boykov-Kolmogorov Algorithm
- Title（参考訳）: Boykov-Kolmogorovアルゴリズムのための高速かつコンパクトなグラフカット
- Authors: Christian Møller Mikkelstrup, Anders Bjorholm Dahl, Philip Bille, Vedrana Andersen Dahl, Inge Li Gørtz,
- Abstract要約: ボヤコフ・コルモゴロフアルゴリズム(BK)を理論的・実用的両面から再検討する。
高速かつコンパクトなBK (fcBK) アルゴリズムを提案し,時間的複雑性を$O(m|C|)$とする。
我々は,BKアルゴリズムを総合的なベンチマークで評価する場合,BKアルゴリズムの実装が最速であることが確認された。
- 参考スコア（独自算出の注目度）: 7.899257236779216
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Computing a minimum $s$-$t$ cut in a graph is a solution to a wide range of computer vision problems, and is often done using the Boykov-Kolmogorov (BK) algorithm. In this paper, we revisit the BK algorithm from both a theoretical and practical point of view. We improve the analysis of the time complexity of the BK algorithm to $O(mn|C|)$ and propose a new algorithm, the fast and compact BK (fcBK) algorithm, with a time complexity of $O(m|C|)$, where $m$, $n$, and $|C|$ are the number of edges, number of vertices, and the capacity of the cut, respectively. We additionally propose a compact graph representation that allows our implementation to find a minimum $s$-$t$ cut in a graph with upwards of $10^9$ vertices and $10^{10}$ edges on a machine with 128 GB of memory. We find our implementation of the BK algorithm to be the fastest available implementation of the BK algorithm when evaluating on a comprehensive set of benchmark datasets, highlighting the importance of memory-efficient implementations. We make our implementations publicly available for further research and implementation development within minimum $s$-$t$ cut algorithms.
- Abstract（参考訳）: グラフにおける最小$s$-$t$の計算は、幅広いコンピュータビジョン問題の解であり、ボイコフ・コルモゴロフアルゴリズム(英語版)(BK)を用いて行われることが多い。
本稿では,BKアルゴリズムを理論的・実用的両面から再検討する。
我々は、BKアルゴリズムの時間複雑性を$O(mn|C|)$に改善し、新しいアルゴリズム、高速でコンパクトなBK(fcBK)アルゴリズムを提案し、時間複雑性は$O(m|C|)$で、$m$、$n$、$|C|$はそれぞれエッジ数、頂点数、カット容量である。
さらに,128GBのマシン上で10^9$頂点と10^10}$エッジのグラフで最小$s$-$t$カットを実現できるグラフ表現を提案する。
我々は,BKアルゴリズムの実装をベンチマークデータセットの包括的集合上で評価する際に,BKアルゴリズムの最も高速な実装とみなし,メモリ効率のよい実装の重要性を強調した。
私たちは、最低$s$-$t$カットアルゴリズムで、さらなる研究と実装開発のために実装を公開します。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Fast Maximum $k$-Plex Algorithms Parameterized by Small Degeneracy Gaps [30.06993761032835]
最大$k$-plex問題は、グラフマイニングやコミュニティ検出といったアプリケーションでは重要であるが、計算的に困難である。
我々は、入力グラフのサイズで最悪のランニング時間を持ち、$g_k(G)$で指数関数的な$g_k(G)$でパラメータ化された正確なアルゴリズムを示す。
我々はさらに議論を、より小さなパラメータ$cg_k(G)$、コミュニティの世代境界と最大$k$-plexのサイズの間のギャップにまで拡張します。
論文 参考訳（メタデータ） (2023-06-23T01:28:24Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Scalable Differentially Private Clustering via Hierarchically Separated
Trees [82.69664595378869]
我々は,最大$O(d3/2log n)cdot OPT + O(k d2 log2 n / epsilon2)$,$epsilon$はプライバシ保証であることを示す。
最悪の場合の保証は、最先端のプライベートクラスタリング手法よりも悪いが、提案するアルゴリズムは実用的である。
論文 参考訳（メタデータ） (2022-06-17T09:24:41Z) - Review of Serial and Parallel Min-Cut/Max-Flow Algorithms for Computer
Vision [6.574107319036238]
Hochbaum pseudoflowアルゴリズムは最速のシリアルアルゴリズムであり、Boykov-Kolmogorovアルゴリズムは最もメモリ効率が高い。
既存の min-cut/max-flow アルゴリズムは、大きな問題ではシリアルアルゴリズムを著しく上回るが、中小問題ではオーバーヘッドが増大する。
論文 参考訳（メタデータ） (2022-02-01T14:06:27Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。
We show that our method with depth $w$ run in $O(pw+3) $ time。
また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
論文 参考訳（メタデータ） (2020-11-06T21:56:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。