China
Africa
Explore chapters and articles related to this topic
Specialized Algorithms for Maximum Flow and Minimum Cut
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
The minimum cut problem is a natural model for minimizing the cost of interdiction of a transportation network. Suppose we want to interdict all routes from s to t by bombing some of the arcs. The cost of destroying arc (i,j) is uij, measured in the expected number of planes required or lost. Then the minimum s−t cut tells us which arcs to destroy to minimize our cost.
Minimum cost flow problems
Published in V. K. Balakrishnan, Network Optimization, 2019
It is obvious that any path between s* and t* in G* is an s–t cut in G and vice versa. By definition, the capacity of an edge between i* and j* in G* is the capacity of an edge in G which is common to the sets of boundaries of the faces which correspond to i* and j*. Consequently, the capacity of an s–t cut in G is equal to the length of the corresponding path between s* and t*. Thus a shortest path between s* and t* in the dual network will define a minimum s–t cut in the given network. Consequently, the cut value of this minimum cut will give the flow value of a maximum flow in the given network. What is not immediately obvious is the fact that any shortest path between s* and t* in the dual network will also define an optimal flow in the primal network. This is the subject of our next theorem.
Level Set Methods in Segmentation of SDOCT Retinal Images
Published in Ayman El-Baz, Jasjit S. Suri, Level Set Method in Medical Imaging Segmentation, 2019
N Padmasini, R Umamaheswari, Yacin Sikkandar Mohamed, Manavi D Sindal
Graph based methods find the global minimum cut of the segmentation graph, which is constructed with a regional term and a boundary term. Garvin [83] proposed a 3D graph search method by constructing a geometric graph with edge and regional information. Five intraretinal layers were successfully segmented. This method was extended in [80], which combined graph theory and dynamic programming to segment the intraretinal layers. Eight retinal layer boundaries were located. Although these methods provide good segmentation accuracy, they cannot segment all layer boundaries simultaneously and the processing speed is relatively slow. [84] proposed a parallel graph search method to overcome these limitations. Kafieh et al., [85] proposed coarse grained diffusion maps relying on regional image texture without requiring edge based image information. Ten layers were segmented accurately. However, this method has high computational complexity and cannot work well for abnormal images.
NP-completeness of cell formation problem with grouping efficacy objective
Published in International Journal of Production Research, 2020
Mikhail V. Batsyn, Ekaterina K. Batsyna, Ilya S. Bychkov
Another observation we have is that the BGEP can be also formulated as the problem of partitioning a graph into a set of quasi-biclques. The simplest graph partitioning problem is the Vertex Colouring Problem, which partitions the complementary graph into a set of cliques. Another well-known graph partitioning problem is the Minimum Cut Problem. The connection with it has been successfully used in the CFP exact algorithm by Krushinsky and Goldengorin (2012). So graph partitioning algorithms also present an interesting research direction along with graph editing ones.