Maximum Capacity-based Minimum Cut Algorithm

Sang-Un, Lee

KJC Korea
Journal Central

Journal of The Korea Society of Computer and Information 2021 KCI Impact Factor : 0.62

Korean | English

pISSN : 1598-849X / eISSN : 2383-9945

http://journal.kci.go.kr/jksci

BACK
TOP

Home > Explore Content > All Issues > Article View

16 of 18

Maximum Capacity-based Minimum Cut Algorithm

Journal of The Korea Society of Computer and Information
Abbr : JKSCI
2011, 16(5), pp.153-162

Publisher : The Korean Society Of Computer And Information
Research Area : Computer Science

Sang-Un, Lee ¹

¹강릉원주대학교

ABSTRACT
열림/닫힘 버튼

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.
KEYWORDS
열림/닫힘 버튼

Max-flow/Min-cut, Flow-based, Deterministic Algorithm, Contraction Algorithm, Construction Algorithm

Statistics

242 Viewed

22 Downloaded

Tools

Print this page

Download PDF

Export Citation

Sharing

Facebook

Twitter

Issue List

Vol.27 No.7

Vol.27 No.6

Vol.27 No.5

Citation status

KCI Citation Counts (3)
열림/닫힘 버튼
REFERENCES (14)
열림/닫힘 버튼
* 2021년 이후 발행 논문의 참고문헌은 현재 구축 중입니다.

[web] J. W. Chinneck / 2000 / Practical Optimization: A Gentle Introduction / http://www.sce.carleton.ca/faculty/chinneck/ po.html

[book] T. H. Cormen / 2005 / Introduction to Algorithms, 2nd Ed., Section 26: Maximum Flow / MIT Press : 643~698

[book] B. Korte / 2008 / Combinatorial Optimization: Theory and Algorithm, Section 8.1 Maximum-Flow Min-Cut Theorem / Springer-Verlang : 166~186

[book] D. Wagner / 2003 / CS 170: Efficient Algorithms and Intractable Problems / UC Berkeley

[journal] H. Nagamochi / 1992 / Computing Edge Connectivity in Multigraphs and Capacitated Graphs / SIAM Journal of Discrete Mathematics 5(1) : 54~66

[journal] D. R. Karger / 1996 / A New Approach to the Minimum Cut Problem / Journal of the ACM 43(4) : 601~640

[web] D. S. Hochbaum / 1999 / The Minimum/Maximum Cut Problem / UC Berkeley / http://riot.ieor.berkeley.edu/riot/Applications/ WeightedMinCut/

[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

[web] Wikipedia / 2007 / Edmonds-KrapAlgorithm / Wikimedia Foundation Inc. / http://en.wikipedia.org/wiki/Edmonds_Krap_Algorithm

[web] K. Ikeda / 2005 / Mathematical Programming / http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/ maxflow/MaxflowApp. shtml

[web] WWL.Chen / 2003 / Discrete Mathematics / http://www.maths.mq.edu.au/~wchen/ /lndmfolder/ lndm.html

[web] A. Schrijver / 2004 / On the History of the Transportation and Maximum Flow Problems / University of Amsterdam / http://homepages.cwi.nl/~lex/files/histrpclean.pdf.Departmentof Mathematics