China
Africa
Explore chapters and articles related to this topic
Minimum cost flow problems
Published in V. K. Balakrishnan, Network Optimization, 2019
Let G = (V, E) be a digraph with a source s and a sink t. A set W of intermediate vertices in G is an s−t vertex-separating set in G if there is no directed path from s to t in the subgraph obtained from G after deleting from V all the vertices belonging to W. The digraph G is said to be k-vertex-connected from s to t if there exists an s−t vertex-separating set of cardinality k and no set with less than k intermediate vertices is an s−t vertex-separating set. In other words, G is k-vertex-connected from s to t if and only if, for any set W of k − 1 intermediate vertices, there should be a directed path from s to t which would not use any vertices from the set W. A set F of arcs in G is an s−t arc-separating set in G if there is no directed path from s to t in the subgraph obtained from G after deleting from Ε all the arcs belonging to F. The digraph G is said to be k-arc-connected from s to t if there exists an s−t arc-separating set of cardinality k and no set with less than k arcs is an s−t arc-separating set. A set C of arcs is an s−t cut in G if C is the set of all arcs in G directed from a vertex in a set S (which contains s and does not contain t) to a vertex in Τ = V − S. Any s−t cut is an s−t arc-separating set. Two directed paths from s to t in the digraph are said to be vertex-disjoint if they have no vertices in common other than s and t, and arc-disjoint if they have no arcs in common. The definitions of these concepts in the case of undirected graphs are analogous.
The g-good-neighbour conditional diagnosability of enhanced hypercube under PMC model
Published in International Journal of Parallel, Emergent and Distributed Systems, 2020
Hui Yu, Yanze Huang, Limei Lin, Jin'e Li, Riqing Chen
Given a graph G, and a subset F of . If G−F is disconnected, F is called a separating set, namely vertex-cut. A separating set F is called a k-separating set if . The maximal connected subgraphs of G−F are called components. A component is trivial if it has no edges. Otherwise, it is nontrivial. The connectivity of G is defined as the minimum k for which G has a k-separating set. Otherwise is defined as n−1 if . A graph G is said to be k-connected if . A k-separating set is called to be the minimum if .