(An) arc-squeezing approach to cut-tree construction for undirected networks = 아크병합에 의한 무방향네트웍의 최대흐름용량분석

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 344
  • Download : 0
An undirected network with n nodes has at most n(n-1)/2 maximum flow values, each being represented in one of n-1 distinct flow values. Defining a free are as an arc in a cycle which is not included in other cycles, it is shown that such a free arc can be squeezed into the rest of the arcs in the cycle with the node-to-node flow still reserved in the network. Then, an arc-squeezing procedure is exploited to break all the cycles contained in the network by its implementing sequentially on each of them and finally to construct a cut-tree, directly transformed from the network. By the arc-squeezing algorithm, multi-terminal network flow problems can be solved in the computational complexity of O(n3), which is much more efficient than any other maximum flow algorithms.
Advisors
Sung, Chang-Supresearcher성창섭researcher
Description
한국과학기술원 : 산업공학과,
Publisher
한국과학기술원
Issue Date
1991
Identifier
67914/325007 / 000871716
Language
eng
Description

학위논문(석사) - 한국과학기술원 : 산업공학과, 1991.8, [ [ii], 42 p. ]

URI
http://hdl.handle.net/10203/41374
Link
http://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=67914&flag=dissertation
Appears in Collection
IE-Theses_Master(석사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0