Maximum Capacity-based Minimum Cut Algorithm

Sang-Un, Lee

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
REFERENCES (14)

[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
KCI Citation (3)

KJC Korea
Journal Central

Statistics

Tools