China
Africa
Explore chapters and articles related to this topic
DTN Coding
Published in Aloizio Pereira da Silva, Scott Burleigh, Katia Obraczka, Delay and Disruption Tolerant Networks, 2019
Marius Feldmann, Felix Walter, Tomaso de Cola, Gianluigi Liva
This theorem states that the maximum flow between any two nodes in a network with given edge capacities is equal to the so-called minimum cut of the network. A cut of a network is a partition of it into two disjoint sets of nodes by removing all edges connecting the two node sets. A minimum cut in a flow network is a cut that is minimal in the sense of the capacity that the removed edges have in sum. Thus, the minimum cut in the network depicted in Figure 6.1 between node A and node E is 2, if we assume that the capacity of each edge is 1. Consequently, it is sufficient to remove specific edges with a total capacity of 2 to separate the source from the sink node. In the case of unicast communication between two nodes in a flow network, a path with maximum flow can be computed using the Ford-Fulkerson algorithm [117]. In the case of multicast communication, the situation is different: Using regular routing, the upper bound defined by the max-flow cannot be reached in all cases. In cases where it can be reached, the underlying problem (packing Steiner trees) is NP-hard and thus computationally expensive (see e.g. [295]). In contrast, the application of network coding is a straightforward approach in order to reach this upper bound in any case, as soon as the amount L of receiving nodes is greater than 1. Ahlswede et al. state in [21], p. 3: “For L ≥ 2, network coding is in general necessary in an optimal multicast scheme.” This core feature makes network coding very interesting for multi-hop multicast networks.
Graph theory concepts and definitions used in image processing and analysis
Published in Olivier Lézoray, Leo Grady, Image Processing and Analysis with Graphs, 2012
A flow is called a maximum flow if and only if the corresponding residual graph is disconnected (i.e., there is no augmenting path). There are several algorithms for finding maximum flows, but we present the classic algorithm proposed by Ford and Fulkerson [18]. The principle of the Ford–Fulkerson algorithm is to add flow along one path as long as there exists an augmenting path in the graph. Figure 1.10 provides the algorithm along with one step of generating an augmenting path. In computer vision, the use of maximum-flow/min-cut solutions to solve problems is typically referred to as graph cuts, following the publication by Boykov et al. [19]. Furthermore, the Ford–Fulkerson algorithm was found to be inefficient for many computer vision problems, with the algorithm by Boykov and Kolmogorov generally preferred [20].
Partitioning and Clustering
Published in Charles J. Alpert, Dinesh P. Mehta, Sachin S. Sapatnekar, Handbook of Algorithms for Physical Design Automation, 2008
The idea behind bipartitioning is to separate G into two blocks (not necessarily the same size) such that s ∈ C1 and t ∈ C2 where the netcut is given by ∑x∈C1,y∈C2c(x,y). The following theorem links computing the maximum flow to the netcut. Theorem 3 MinFlow MaxCut: For any network, the maximum flow value from s to t is equal to the minimum cut capacity for all cuts separating s and t
Product–machine qualification using a process flexibility strategy considering capacity loss
Published in IISE Transactions, 2023
Suppose there is a source node s on the demand side connecting all demand nodes with arc capacities limited by respectively, and a sink node t on the capacity side connecting all capacity nodes with each arc capacity limited by 1-λ. Objective model (1) can then be equivalently transformed into a maximum-flow model, and the maximum value of the flow will become the objective (i.e., the performance of the configuration). Once the maximum-flow model has been defined, Inequality (39) can be demonstrated by the well-known maximum-flow minimum-cut theorem: the maximum value of the flow from a source node s to a sink node t in a capacitated network equals the minimum capacity among all s-t cuts. To demonstrate Inequality (39), it can be shown that, for any candidate cut u in the simple closed-dedicated-chain configuration, a corresponding cut u′ always exists in the corresponding 2-chain, satisfying the following: where and represent the capacity of cut u in the simple closed-dedicated-chain and cut u’ in the corresponding 2-chain configuration, respectively. It is then obvious that the simple closed-dedicated-chain configuration cannot be optimal. To demonstrate Inequality (40), the following lemma is proposed:
Generalized derivatives of computer programs
Published in Optimization Methods and Software, 2022
Matthew R. Billingsley, Paul I. Barton
There are many programs which can be written as imperative programs described by Definition 2.1, and for which the overall program is L-smooth, but contain subprograms that are not L-smooth. Consider for example, the Ford–Fulkerson algorithm for finding a maximum flow through a graph. Since the maximum flow problem is a linear program, the optimal solution is L-smooth with respect to the right-hand side of the constraints [13], in this case the capacities of the edges. However, in the Ford–Fulkerson algorithm there is an operation in which the graph is reconstructed, and is represented as a discontinuous (and thus not L-smooth) program, meaning that LD-derivatives cannot be calculated. In this way, we have a program which itself is L-smooth, but is not composed of L-smooth subprograms.
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.