The minimum cut problem is to minimize , that is, to determine source and sink such that the capacity of the cut is minimal. The flow-based algorithm is mostly used to find the bottleneck arcs by calculating flow network, and does not presents the minimum cut. This paper suggests an algorithm that simply includes the maximum capacity vertex to adjacent set or and finds the minimum cut without obtaining flow network in advance. On applying the suggested algorithm to 13 limited graphs, it can be finds the minimum cut value with simply and correctly.
[thesis]
M. S. Levine
/ 1997
/ Experimental Study of Minimum Cut Algorithms
/ 석사
/ MIT
[confproc]
G. Deng
/ 2009
/ An Improved Algorithm for Maximum Flow Problem
/ International Conference on Communications, Circuits and Systems(ICCAS)
: 591~594
[journal]
A. V. Goldberg
/ 1988
/ A New Approach to the Maximum Flow Problem
/ Journal of the ACM
35
: 921~940
@article{ART001554794}, author={Sang-Un, Lee}, title={Maximum Capacity-based Minimum Cut Algorithm}, journal={Journal of The Korea Society of Computer and Information}, issn={1598-849X}, year={2011}, volume={16}, number={5}, pages={153-162}
TY - JOUR AU - Sang-Un, Lee TI - Maximum Capacity-based Minimum Cut Algorithm JO - Journal of The Korea Society of Computer and Information PY - 2011 VL - 16 IS - 5 PB - The Korean Society Of Computer And Information SP - 153 EP - 162 SN - 1598-849X AB - The minimum cut problem is to minimize , that is, to determine source and sink such that the capacity of the cut is minimal. The flow-based algorithm is mostly used to find the bottleneck arcs by calculating flow network, and does not presents the minimum cut. This paper suggests an algorithm that simply includes the maximum capacity vertex to adjacent set or and finds the minimum cut without obtaining flow network in advance. On applying the suggested algorithm to 13 limited graphs, it can be finds the minimum cut value with simply and correctly. KW - Max-flow/Min-cut;Flow-based;Deterministic Algorithm;Contraction Algorithm;Construction Algorithm DO - UR - ER -
Sang-Un, Lee. (2011). Maximum Capacity-based Minimum Cut Algorithm. Journal of The Korea Society of Computer and Information, 16(5), 153-162.
Sang-Un, Lee. 2011, "Maximum Capacity-based Minimum Cut Algorithm", Journal of The Korea Society of Computer and Information, vol.16, no.5 pp.153-162.
Sang-Un, Lee "Maximum Capacity-based Minimum Cut Algorithm" Journal of The Korea Society of Computer and Information 16.5 pp.153-162 (2011) : 153.
Sang-Un, Lee. Maximum Capacity-based Minimum Cut Algorithm. 2011; 16(5), 153-162.
Sang-Un, Lee. "Maximum Capacity-based Minimum Cut Algorithm" Journal of The Korea Society of Computer and Information 16, no.5 (2011) : 153-162.
Sang-Un, Lee. Maximum Capacity-based Minimum Cut Algorithm. Journal of The Korea Society of Computer and Information, 16(5), 153-162.
Sang-Un, Lee. Maximum Capacity-based Minimum Cut Algorithm. Journal of The Korea Society of Computer and Information. 2011; 16(5) 153-162.
Sang-Un, Lee. Maximum Capacity-based Minimum Cut Algorithm. 2011; 16(5), 153-162.
Sang-Un, Lee. "Maximum Capacity-based Minimum Cut Algorithm" Journal of The Korea Society of Computer and Information 16, no.5 (2011) : 153-162.