The capacity (i.e., maximum flow) of a unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of undirected graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. The feature of our approach is to utilize the correspondence between the cut space of an undirected graph and a binary LDGM (low-density generator-matrix) code. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.

It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.

The connectivity augmentation problem asks to add to a given graph the smallest number of new edges so that the edge- (or vertex-) connectivity of the graph increases up to a specified value k. The problem has been extensively studied, and several efficient algorithm have been discovered. We survey the recent development of the algorithms for this problem. In particular, we show how the minimum cut algorithm due to Nagamochi and Ibaraki is effectively applied to solve the edge-connectivity augmentation problem.

For the correctness of the minimum cut algorithm proposed in [H. Nagamochi and T. Ibaraki, Computing edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, 5, 1992, pp. 54-66], several simple proofs have been presented so far. This paper gives yet another simple proof. As a byproduct, it can provide an O(m log n) time algorithm that outputs a maximum flow between the pair of vertices s and t selected by the algorithm, where n and m are the numbers of vertices and edges, respectively. This algorithm can be used to speed up the algorithm to compute DAGs,t that represents all minimum cuts separating vertices s and t in a graph G, and the algorithm to compute the cactus Γ(G) that represents all minimum cuts in G.

Two algorithms for minimum cut linear arrangement of a class of graphs called p-q dags are proposed. A p-q dag represents the connection scheme of an adder tree, such as Wallace tree, and the VLSI layout problem of a bit slice of an adder tree is treated as the minimum cut linear arrangement problem of its corresponding p-q dag. One of the two algorithms is based on dynamic programming. It calculates an exact minimum solution within nO(1) time and space, where n is the size of a given graph. The other algorithm is an approximation algorithm which calculates a solution with O(log n) cutwidth. It requires O(n log n) time.

In this paper, we propose an algorithm of O(|V|min{k,|V|,|A|}|A|) time complexity for finding all k-edge-connected components of a given digraph D=(V,A) and a positive integer k. When D is symmetric, incorporating a preprocessing reduces this time complexity to O(|A|+|V|2+|V|min{k,|V|}min{k|V|,|A|}), which is at most O(|A|+k2|V|2).

This paper deals with the problem of assigning tasks to the processors of a multiprocessor system such that the sum of execution and communication costs is minimized. If the number of processors is two, this problem can be solved efficiently using the network flow approach pioneered by Stone. This problem is, however, known to be NP-complete in the general case, and thus intractable for systems with a large number of processors. In this paper, we propose a network flow approach for the task assignment problem in homogeneous hypercube networks, i.e., hypercube networks with functionally identical processors. The task assignment problem for an n-dimensional homogeneous hypercube network of N (=2n) processors and M tasks is first transformed into n two-terminal network flow problems, and then solved in time no worse than O(M3 log N) by applying the Goldberg-Tarjan's maximum flow algorithm on each two-terminal network flow problem.