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.
Interpretability and Explainability Techniques for Transformers
Published in Uday Kamath, Kenneth L. Graham, Wael Emara, Transformers for Machine Learning, 2022
Uday Kamath, Kenneth L. Graham, Wael Emara
A flow network is a directed graph with a “capacity” affiliated with every edge in a graph as per the graph theory. A maximum flow algorithm finds a flow with the maximum possible value between any given source and the sink given the flow network. In this technique, when the graph network mapping to the flow network of the transformers happens, with the edges as the attention weights; the maximum flow algorithm can compute the maximum attention flow from any node of any layer to the input nodes(tokens).
From state diagrams to sequence diagrams: a requirements acquisition approach
Published in International Journal of Computers and Applications, 2019
Bingyang Wei, Harry S. Delugach, Yi Wang
A flow networkG = (V, E) is a single-source and single-sink directed acyclic graph. Flow generated by the vertex s reaches vertex t by traveling through all the other vertices and edges connecting them in the graph. Think of a flow network as a traffic network where each edge is carrying a certain number of flow units. In a flow network, each edge is associated with a lower flow requirement and a current flow (see Figure 4), the current flow that an edge carries must be no less than the lower flow requirement at any time. Another important property about a flow network is that the amount of flow entering a vertex through incoming edges must be equal to that of leaving through the outgoing edges. For example, in Figure 4, two units of flow enters vertex State A in the flow network, then the summation of flow on each outgoing edges is also two units.
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 .