China 
Africa 
Explore chapters and articles related to this topic
A Parametric Maximum Flow Approach for Discrete Total Variation Regularization
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
Chambolle Antonin, Jérôme Darbon
which is the binary energy to optimize up to a constant. In other words, minimizing a binary energy of the form of (4.11) can be performed by computing the minimum cut of its associated network. Such a cut can be computed in polynomial time. It turns out that the dual problem to the minimum cut problem is the so-called maximum flow problem of maximizing F(f) among all feasible flows. Hence, the maximum flow problem consists in sending the maximum amount of flow from the source to the sink such that the flow is feasible and that the divergence is free at all nodes except the source and the sink. The best theoretical time complexity algorithms for computing a maximum-flow on a general graph are based on a “push-relabel” approach [23, 24] (more recent algorithms can compute faster approximate flows [25]). However, for graph with few incident arcs (as it is the generally case for image processing and computer vision problems) the augmenting path approach yields excellent practical time [26].
Specialized Algorithms for Maximum Flow and Minimum Cut
Published in Craig A. Tovey, Linear Optimization and Duality, 2020
The maximum flow problem is about sending as much as possible through a network whose arcs have upper bounds on flow. Let G=(V,E) be a graph with nodes V, two distinct special nodes s∈V,t∈V, directed arcs E, and upper bounds uij≥0 on each arc (i,j)∈E. The goal is to set flow values on the arcs of G to maximize the amount of flow that originates at s and arrives at t. Flow is not permitted to originate at any node other than s, which is called the source, nor to accumulate at any node other than t, which is called the sink. Figure 13.1 shows a small example for which the upper bounds are usa=5,uat=18, usb=20, uba=30, ubt=6, and the maximum possible s−t flow is 24.
Connectivity maintenance with application to target search
Published in SICE Journal of Control, Measurement, and System Integration, 2021
A method using the maximum flow problem is used to derive the vertex connectivity in [11]. The maximum flow problem is to find the maximum value of the total flow from the inflow point s to the outflow point t when a weighted graph is given. The s, t vertex connectivity can be obtained by the following procedure in global manner.
Interdicting layered physical and information flow networks
Published in IISE Transactions, 2018
Nail Orkun Baycik, Thomas C. Sharkey, Chase E. Rainwater
Since some of the entities in the physical flow network are also in the information flow network, there exists a connection between the two networks, which results in an interdependency between them. To capture this interdependency, we define set ID as the collection of nodes that appear in both networks and the flow through node i in the physical flow network depends on an adequate amount of demand being met at the corresponding node i′ in the information flow network, where (i, i′) ∈ ID. We represent node i as an arc (i, i1) in order to capture the interdependencies only on the arcs of the network (see Ahuja et al. (1993) for details of this traditional node expansion technique). We define a set S′⊆N′ as the set of information supply nodes and a set D′⊆N′ as the set of information demand nodes, and for each i′ ∈ D′ there exists a node i ∈ N such that (i, i′) ∈ ID and an arc (i, i1) ∈ A that corresponds to the node that is not operational if the demand of node i′ ∈ D′ is not satisfied. The information supply at each node i′ is represented by . We define a set S as the set of supply nodes in the physical flow network and reformulate the physical flow network by adding a source node s ∈ N that is connected to all supply nodes in set S, a sink node t ∈ N that is connected to the demand nodes in set D in the physical flow network, and an arc (t, s) from t to s (see Ahuja et al. (1993) for details on this traditional reformulation of the problem of maximizing flow from a set of supply nodes to a set of demand nodes as a maximum flow problem). The decision variable xij is the amount of flow on arc (i, j). If the demand, , on an information node i′ ∈ D′ is not met, a slack variable is positive and zero otherwise. Therefore, the decision variable , which connects the demand node i′ ∈ D′ in the information flow network to node i ∈ D in the physical flow network, becomes one if the demand of node i′ is satisfied (i.e., ) and zero otherwise. To convert the information flow network into a structure similar to the maximum flow problem, we add in a super-source node s′ ∈ N′ and super-sink node t′ ∈ N′, arcs connecting the super-source node to the supply nodes, and the arcs connecting the demand nodes to the super-sink node. Note that in this maximum flow formulation, the flow on arc (i′, t′) with i′ ∈ D′ represents the amount of demand met at node i′. In this case, demand is not met at i′ if .