ANOTHER SIMPLE PROOF OF THE VALIDITY OF NAGAMOCHI AND IBARAKI'S MIN-CUT ALGORITHM AND QUEYRANNE'S EXTENSION TO SYMMETRIC SUBMODULAR FUNCTION MINIMIZATION

スポンサーリンク

概要

• 論文の詳細を見る

• M. Stoer and F. Wagner and independently A. Frank have found a simple proof of the validity of Nagamochi and Ibaraki's min-cut algorithm. This note points out some nice property of the behavior of Nagamochi and Ibaraki's min-cut algorithm, which also gives another simple proof of the validity of their algorithm. The proof relies only on the symmetric submodularity of the cut function. Hence, it also gives another simple proof of the validity of Queyranne's extension of Nagamochi and Ibaraki's algorithm to symmetric submodular function minimization.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Fujishige Satoru

  Division of Systems Science Department of Systems and Human Science Graduate School of Enginecring S

• Fujishige Satoru

  Osaka University

• 藤重 悟

  Kyoto University

関連論文

• BALANCED BISUBMODULAR SYSTEMS AND BIDIRECTED FLOWS
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER A FINITE JUMP SYSTEM
• A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON
• New Maximum Flow Algorithms by MA Orderings and Scaling
• A TREE PARTITIONING PROBLEM ARISING FROM AN EVACUATION PROBLEM IN TREE DYNAMIC NETWORKS
• Optimal Sink Location Problem for Dynamic Flows in a Tree Network(Special Section on Discrete Mathematics and Its Applications)
• 劣モジュラ関数最小化のアルゴリズム:ブレイクスルーと周辺の話題 (特集 アルゴリズムの新展開--理論から工学へ)
• ANOTHER SIMPLE PROOF OF THE VALIDITY OF NAGAMOCHI AND IBARAKI'S MIN-CUT ALGORITHM AND QUEYRANNE'S EXTENSION TO SYMMETRIC SUBMODULAR FUNCTION MINIMIZATION
• Algorithms for Submodular Flows(Special Issue on Algorithm Engineering : Surveys)

スポンサーリンク