Journal of the Korea Society of Computer and Information (한국컴퓨터정보학회논문지)

Korean Society of Computer Information (한국컴퓨터정보학회)
권호 표지
DOI QR코드

DOI QR Code

Maximum Capacity-based Minimum Cut Algorithm

최대 수용량-기반 최소절단 알고리즘

  • Lee, Sang-Un (Dept. of Multimedia Science, Gangneung-Wonju National University)
  • 이상운 (강릉원주대학교 멀티미디어공학과)
  • Received : 2011.01.14
  • Accepted : 2011.02.10
  • Published : 2011.05.31
Download PDF
⟨ Previous Next ⟩

Abstract

The minimum cut problem is to minimize c(S,T), that is, to determine source S and sink T such that the capacity of the S-T 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 S or T 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 $_{\min}c$(S, T) with simply and correctly.

최소 절단 문제는 공급처 S에서와 수요처 T로의 흐름 용량이 최소가 되는 지점들을 절단하는 문제이다. 망의 병목지점을 찾는 방법은 대부분 유동망을 계산하여 최소 절단값을 찾는 유동-기반 알고리즘이 적용되고 있다. 이 알고리즘은 최소절단은 제시하지 않는 단점이 있다. 본 논문은 유동망을 구하지 않고 망으로부터 직접 최대 수용량을 가진 정점을 인접한 S 또는 T로 병합하는 방법으로 최소 절단값을 찾는 간단한 알고리즘이다. 13개의 한정된 그래프에 적용한 결과 제안된 알고리즘은 간단하면서도 정확하게 최소 절단 값 $_{\min}c$(S, T)을 찾을 수 있었다.

Keywords

References

  1. J. W. Chinneck, "Practical Optimization: A Gentle Introduction," http://www.sce.carleton.ca/faculty/chinneck/po.html, 2000.
  2. T. H. Cormen, C. E. Leiserson, R. L. Riverst, and C. Stein, "Introduction to Algorithms," 2nd Ed., Section 26: Maximum Flow," pp. 643-698, MIT Press, 2005.
  3. B. Korte and J. Vygen, "Combinatorial Optimization: Theory and Algorithm, Section 8.1 Maximum-Flow Min-Cut Theorem," 4th Ed., pp. 166-186, Springer-Verlang, 2008.
  4. D. Wagner, "CS 170: Efficient Algorithms and Intractable Problems," UC Berkeley, 2003.
  5. H. Nagamochi and T. Ibaraki, "Computing Edge Connectivity in Multigraphs and Capacitated Graphs," SIAM Journal of Discrete Mathematics, Vol. 5, No. 1, pp. 54-66, 1992. https://doi.org/10.1137/0405004
  6. D. R. Karger and C. Stein, "A New Approach to the Minimum Cut Problem," Journal of the ACM, Vol. 43, Issue. 4, pp. 601-640, 1996. https://doi.org/10.1145/234533.234534
  7. D. S. Hochbaum, "The Minimum/MaximumCut Problem, " RIOT, UC Berkeley, http://riot.ieor.berkeley.edu/riot/Applications/WeightedMinCut/, 1999.
  8. M. S. Levine, "Experimental Study of Minimum Cut Algorithms," Master Thesis, MIT, 1997.
  9. G. Deng, M. Tang, and G. Chen, "An Improved Algorithm for Maximum Flow Problem," International Conference on Communications, Circuits and Systems(ICCAS), pp. 591-594, 2009.
  10. A. V. Goldberg, "A New Approach to the Maximum Flow Problem," Journal of the ACM, Vol. 35, pp. 921-940, 1988. https://doi.org/10.1145/48014.61051
  11. Wikipedia,"Edmonds-KrapAlgorithm," http://en.wikipedia.org/wiki/Edmonds_Krap_Algorithm, Wikimedia Foundation Inc., 2007.
  12. K. Ikeda, "Mathematical Programming," Dept. InformationScience and Intelligent Systems, The University of Tokushima, http://www-b 2.is.tokushima-u.ac.jp/-ikeda/suuri/maxflow/MaxflowApp.shtml. 2005.
  13. WWL.Chen,"Discrete Mathematics," Department of Mathematics, Division of ICS, Macquarie University, Australia, http://www.maths.mq.edu.au/-wchen//lndmfolder/lndm.html, 2003.
  14. A. Schrijver, "On the History of the Transportation and Maximum Flow Problems," http://homepages. cwi.nl/-lex/files/histrpclean.pdf.Departmentof Mathematics, University of Amsterdam, Netherlands, 2004.