A Simple Proof of a Minimum Cut Algorithm and Its Applications
スポンサーリンク
概要
- 論文の詳細を見る
For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several simple proofs have been presented so far. This paper gives yet another simple proof. As a byproduct, it can provide an Ο(mlogn) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAG_<s,t> that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Γ(G) that represents all minimum cuts in G.
- 社団法人電子情報通信学会の論文
- 1999-10-25
著者
-
NAGAMOCHI Hiroshi
Department of Applied Mathematics and Physics, Kyoto University
-
Nagamochi H
Kyoto Univ.
-
Ibaraki Toshihide
Department of Informatics, Kwansei Gakuin University
-
Ibaraki Toshihide
School of Science and Technology, Kwansei Gakuin University
-
ISHII Toshimasa
Department of Gastroenterological Surgery, Saitama International Medical Center, Saitama Medical Uni
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Informatics Kyoto University
-
Ishii Toshimasa
Department Of Gastroenterological Surgery Saitama International Medical Center Saitama Medical Unive
-
Ibaraki T
School Of Science And Technology Kwansei Gakuin University
-
Ibaraki Toshihide
Department Of Applied Mathematics And Physics Faculty Of Engineering Kyoto University
-
Ibaraki Toshihide
Department Of Informatics Kwansei Gakuin University
-
Nagamochi Hiroshi
Department Of Applied Mathematics And Physics Graduate School Of Engineering Kyoto University
関連論文
- Optimization Problems and Algorithms in Double-layered Food Packing Systems
- CONSTRUCTING CACTUS REPRESENTATION FOR ALL MINIMUM CUTS IN AN UNDIRECTED NETWORK
- Generation of Symmetric and Asymmetric Biconnected Rooted Outerplanar Graphs
- Generation of Symmetric and Asymmetric Biconnected Rooted Triangulated Planar Graphs
- 1A1 COMBINATORIAL OPTIMIZATION PROBLEMS AND ALGORITHMS IN DOUBLE-LAYERED FOOD PACKING EQUIPMENTS
- 6B2 AN ITERATED LOCAL SEARCH ALGORITHM FOR THE MULTI-RESOURCE GENERALIZED ASSIGNMENT PROBLEM WITH FLEXIBLE ASSIGNMENT COST(Technical session 6B: General model for scheduling and assignment problem)
- 5B1 A GUIDED LOCAL SEARCH ALGORITHM BASED ON A FAST NEIGHBORHOOD SEARCH FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- Hepatic Metastasis 12 Years after Nephrectomy for Renal Cell Carcinoma
- Constructing a Cactus for Minimum Cuts of a Graph in ★(mn+n^2logn) Time and ★(m) Space (Special Issue on Selected Papers from LA Symposium)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Computing a Minimum Cut in a Graph with Dynamic Edges Incident to a Designated Vertex(Graph Algorithms,Foundations of Computer Science)
- Augmenting a (k-1)-vertex-connected multigraph to an l-edge-connected and k-vertex-connected multigraph
- Multigraph augmentation under biconnectivity and general edge-connectivity requirements
- Optimal augmentation of a 2-vertex-connected multigraph to a k-edge-connected and 3-vertex-connected multigraph
- A Simple Proof of a Minimum Cut Algorithm and Its Applications
- k-Edge and 3-Vertex Connectivity Augmentation in an Arbitrary Multigraph
- Augmenting Edge-Connectivity and Vertex-Connectivity Simultaneously
- Approximating a Generalization of Metric TSP(Graph Algorithms,Foundations of Computer Science)
- Approximation to the Minimum Cost Edge Installation Problem
- A Randomness Based Analysis on the Data Size Needed for Removing Deceptive Patterns
- BI-CRITERIA FOOD PACKING BY DYNAMIC PROGRAMMING(the 50th Anniversary of the Operations Research Society of Japan)
- APPROXIMATING MINIMUM COST MULTIGRAPHS OF SPECIFIED EDGE-CONNECTIVITY UNDER DEGREE BOUNDS(the 50th Anniversary of the Operations Research Society of Japan)
- Performance Analysis of a Collision Detection Algorithm of Spheres Based on Slab Partitioning
- 4C1 SCHEDULING MULTIPROCESSOR TASKS WITH PROMPT SERVICE CONSTRAINTS ON ALIGNED IDENTICAL PROCESSORS
- Worst Case Analysis for Pickup and Delivery Problems with Transfer
- 4A1 A LOCAL SEARCH ALGORITHM FOR ROUTING AND SCHEDULING PROBLEMS WITH TIME WINDOW AND TRAVELING TIME CONSTRAINTS(Technical session 4A : Vehicle routing)
- Orthogonal Drawings for Plane Graphs with Specified Face Areas(Theory of Computer Science and Its Applications)
- 1A2 AN IMPROVED APPROXIMATION ALGORITHM FOR CAPACITATED MULTICAST ROUTINGS IN NETWORKS(Technical session 1A: Combinatorial optimization)
- 5B2 AN ITERATED LOCAL SEARCH ALGORITHM BASED ON NONLINEAR PROGRAMMING FOR THE IRREGULAR STRIP PACKING PROBLEM(Technical session 5B: Packing problem)
- 2B1 A DP-BASED HEURISTIC ALGORITHM FOR THE DISCRETE SPLIT DELIVERY VEHICLE ROUTING PROBLEM(Technical session 2B: Vehicle scheduling and communication)
- A Fast Edge-Splitting Algorithm in Edge-Weighted Graphs(Discrete Mathematics and Its Applications)
- A Note on Approximating the Survivable Network Design Problem in Hypergraphs(Special Issue on Selected Papers from LA Symposium)
- Approximation Algorithms for Multicast Routings in a Network with Multi-Sources(Discrete Mathematics and Its Applications)
- An LP-Based Local Search to the One Dimensional Cutting Stock Problem Using a Given Number of Cutting Patterns
- Construction of Classifiers by Iterative Compositions of Features with Partial Knowledge(Discrete Mathematics and Its Applications)
- ALGORITHMS FOR QUADRATIC FRACTIONAL PROGRAMMING PROBLEMS
- A Fast Algorithm for Cactus Representations of Minimum Cuts
- Solving the Single-Vehicle Scheduling Problems for All Home Locations under Depth-First Routing on a Tree (Special Section on Discrete Mathematics and Its Applications)
- VEHICLE SCHEDULING ON A TREE TO MINIMIZE MAXIMUM LATENESS
- INTERIOR METHODS FOR NONLINEAR MINIMUM COST NETWORK FLOW PROBLEMS
- 1A1 Scheduling of Corrugated Paper Production(Technical session 1A: Combinatorial optimization)
- A PRIMAL CUTTING PLANE ALGORITHM FOR INTEGER FRACTIONAL PROGRAMMING PROBLEMS
- AN ASSIGNMENT PROBLEM ON A NETWORK
- MINIMUM DELAY SEMIJOIN SCHEDULES FOR LOCAL AREA DISTRIBUTED DATABASE SYSTEMS(Mathematical Theories on Computing Schemes and Their Applications)
- Approximability of the Minimum Maximal Matching Problem in Planar Graphs(Graphs and Networks)
- An Approximation of the Minimum Vertex Cover in a Graph
- Approximating the Minmax Rooted-Subtree Cover Problem(Graphs and Networks)
- Minimum Self-Dual Decompositions of Positive Dual-Minor Boolean Functions
- ON THE COMPUTATIONAL EFFICIENCY OF BRANCH-AND-BOUND ALGORITHMS
- PARTIALLY DEFINED BOOLEAN FUNCTIONS WITH APPLICATIONS TO DATA ANALYSIS : A SURVEY
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Dynamic Programming Based Improvement Heuristic for a Repetitive Routing Problem of Grasp-and-Delivery Robots
- Better Approximation Algorithms for Grasp-and-Delivery Robot Routing Problems
- 4A2 NETWORK TRANSFORMATION HEURISTICS FOR MULTI-STORY STORAGE RACK PROBLEMS(Technical session 4A: Material handling system)
- 5B1 IMPROVED IMPLEMENTATION OF AN APPROXIMATION ALGORITHM WITH FACTOR TWO FOR A CYCLIC ROUTING PROBLEM OF GRASP-AND-DELIVERY ROBOTS(Technical session 5B: Routing problems)
- 5B3 APPROXIMATING CYCLIC ROUTING PROBLEMS OF GRASP-AND-DELIVERY ROBOTS IN PRODUCTION OF PRINTED CIRCUIT BOARDS(Technical session 5B: Routing problems)
- Scheduling Capacitated One-Way Vehicles on Paths with Deadlines
- A DP-based Heuristic Algorithm for the Discrete Split Delivery Vehicle Routing Problem