For given integerp, a flow networkNwithn vertices, and sources inN, a problem of finding location ofp sinks inN which maximize the value of maximum flow from sources to sinks is calledp-collection problem. This problem is NP-hard even if a given network is a tree, but a pseudo-polynomial time algorithm is possible for such a network. This paper proposes a new pseudo-polynomial time algorithm for a tree-type network, which is simpler and more efficient than the previous algorithm, and has time complexity of O(p2n2Cc min {Cc,Cd}), whereCc andCd are the maximum edge capacity and the maximum vertex weight, respectively.

Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. We have studied location theory from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. In a previous paper, we have considered location problems, called covering problems and proposed polynomial time algorithms for these problems. These problems are applicable to assigning files to some computers in a computer network. This paper is concerned with a covering problem called the single cover problem defined in the previous paper. First, we define a generalized single cover problem and show that an algorithm proposed in the previous paper can be applicable to solving the generalized single cover problem. Then, we define a single cover problem satisfying cardinality constrains and show that the problem is solved in a polynomial time.

The p-collection problem is where to locate p sinks in a flow network such that the value of a maximum flow is maximum. In this paper we show complexity results of the p-collection problem. We prove that the decision problem corresponding to the p-collection problem is strongly NP-complete. Although location problems (the p-center problem and the p-median problem) in networks and flow networks with tree structure is solvable in polynomial time, we prove that the decision problem of the p-collection problem in networks with tree structure, is weakly NP-complete. And we show a polynomial time algorithm for the subproblem of the p-collection problem such that the degree sum of vertices with degree3 in a network, is bound to some constant K0.

Data flow is a paradigm for concurrent computations in which a collection of parallel processes communicate asynchronously. For nondeterministic data flow networks many semantic models have been defined, however, it is complex to reason about the semantics of a network. In this paper, we introduce a transformation between data flow networks and the LOTOS specification language to make available theories and tools developed for process algebras for the semantic analysis based on traces of the networks. The transformation does not establish a one-to-one mapping between the traces of a data flow network and the LOTOS specification, but maps each network in a specification which usually contains more traces. The obtained system specification has the same set of traces as the corresponding network if they are finite, otherwise also non fair traces are included. Formal analysis and verification methods can still be applied to prove properties of the original data flow network, allowing in case of networks with finite traces to prove also network equivalence.

Location theory on networks is concerned with the problem of selecting the best location in a specified network for facilities. Many studies for the theory have been done. However, few studies treat location problems on networks from the standpoint of measuring the closeness between two vertices by the capacity (maximum flow value) between two vertices. This paper concerns location problems, called covering problems on flow networks. We define two types of covering problems on flow networks. We show that covering problems on undirected flow networks and a covering problem on directed flow networks are solved in polynomial times.