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.

This paper presents a binary neural network approach for link activation problems in multihop radio networks. The goal of the NP-complete problems is to find a conflict-free link activation schedule with the minimum number of time slots for specified communication requirements. The neural network is composed of NM binary neurons for scheduling N links in M time slots. The energy functions and the motion equations are newly defined with heuristic methods. The simulation results through 14 instances with up to 419 links show that the neural network not only surpasses the best existing neural network in terms of the convergence rate and the computation time, but also can solve large scale instances within a constant number of iteration steps.

An s-t flow in a directed network is called uncontrollable, when the flow is representable as a positive sum of elementary s-t path flows. In this paper, we discuss the problem Is a given flow uncontrollable?. We show that the problem is NP-complete.

An ordered binary decision diagram (OBDD) is a directed acyclic graph for representing a Boolean function. OBDDs are widely used in various areas which require Boolean function manipulation, since they can represent efficiently many practical Boolean functions and have other desirable properties. However, there is very little theoretical research on the complexity of constructing an OBDD. In this paper, we prove that the optimal variable ordering problem of a shared BDD is NP-complete, and briefly discuss the approximation hardness of this problem and related OBDD problems.

A clique of a graph G(V,E) is a subset of V such that every pair of vertices is connected by an edge in E. Finding a maximum clique of an arbitrary graph is a well-known NP-complete problem. Recently, several polynomial time energy-descent optimization algorithms have been proposed for approximating the maximum clique problem, where they seek a solution by minimizing the energy function representing the constraints and the goal function. In this paper, we propose the binary neural network as an efficient synchronous energy-descent optimization algorithm. Through two types of random graphs, we compare the performance of four promising energy-descent optimization algorithms. The simulation results show that RaCLIQUE, the modified Boltzmann machine algorithm, is the best asynchronous algorithm for random graphs, while the binary neural network is the best one for k random cliques graphs.

It is known that the problem of determining, given a planar graph G with maximum vertex degree at most 4 and integers m and n, whether G is embeddable in an m n grid with unit congestion is NP-hard. In this paper, we show that it is also NP-complete to determine whether G is embeddable in ak n grid with unit congestion for any fixed integer k 3. In addition, we show a necessary and sufficient condition for G to be embeddable in a 2 grid with unit congestion, and show that G satisfying the condition is embeddable in a 2 |V(G)| grid. Based on the characterization, we suggest a linear time algorithm for recognizing graphs embeddable in a 2 grid with unit congestion.

We define the Reallocation Problem to determine whether we can move products from their current store-houses to target storehouses in a number of moves which is less than or equal to a given number. This problem is defined simply and can be applied to many practical problems. We give necessary and sufficient conditions for feasibility for Reallocation Problems under various conditions, and propose liner time algorithms, when the volume of the products is restricted to 1. Moreover, we show that the Reallocation Problem is NP-complete in the strong sense, when the volume of the products is not restricted.

A 2-switch node network is one of the most fundamental structure among communication nets such as telephone networks and local area networks etc. In this letter, we prove that a problem of designing a 2-switch node network satisfying capacity conditions of switch nodes and their link, which we call 2-switch node network problem, is NP-complete.

Concerning the complexity of tree drawing, the following result of Supowit and Reingold is known: the problem of minimum drawing binary trees under several constraints is NP-complete. There remain, however, many open problems. For example, is it still NP-complete if we eliminate some constraints from the above set? In this paper, we treat tree-structured diagrams. A tree-structured diagrm is a tree with variably sized rectangular nodes. We consider the layout problem of tree-structured diagrams on Z2 (the integral lattice). Our problems are different from that of Supowit and Reingold, even if our problems are limited to binary trees. In fact, our set of constraints and that of Supowit and Reingold are incomparable. We show that a problem is NP-complete under a certain set of constraints. Furthermore, we also show that another problem is still NP-complete, even if we delete a constraint concerning with the symmetry from the previous set of constraints. This constraint corresponds to one of the constraints of Supowit and Reingold, if the problem is limited to binary trees.

For two finite disjoint sets P and Q of strings over an alphabet Σ, an alphabet indexing for P, Q by an indexing alphabet Γ with |Γ||Σ| is a mapping :ΣΓ satisfying (P)(Q), where :Σ*Γ* is the homomorphism derived from . We defined this notion through experiments of knowledge acquisition from amino acid sequences of proteins by learning algorithms. This paper analyzes the complexity of finding an alphabet indexing. We first show that the problem is NP-complete. Then we give a local search algorithm for this problem and show a result on PLS-completeness.

In this paper, it is proven that the following three decision problems on validation of protocols with bounded capacity channels are NP-complete. (1) Given a protocol with the channel capacity being 1, determine whether or not there exist deadlocks in the protocol. (2) Given a protocol with the channel capacity being 1, determine whether or not there exist unspecified receptions in the protocol. (3) Given a protocol with the channel capacity being 2, determine whether or not there exist overflows such that the channel capacity is not bounded by 1 in the protocol. These results suggest that, even when all channeles in a protocol are bounded by 1 or 2, protocol validation should be in general interactable. It also clarifies the boundary of computational complexity of protocol validation problems because the channel capacity 0 does not allow protocols to transmit and recieve messages.

Problems of realizing a vertex-weighted tree with a given weighted tranamission number sequence are discussed in this paper. First we consider properties of the weighted transmission number sequence of a vertex-weighted tree. Let S be a sequence whose terms are pairs of a non-negative integer and a positive integer. The problem determining whether S is the weighted transmission number sequence of a vertex-weighted tree or not, is called w-TNS. We prove that w-TNS is NP-complete, and we show an algorithm using backtracking. This algorithm always gives a correct solution. And, if each transmission number of S is different to the others, then the time complexity of this is only 0( S 2).Next we consider the d2-transmission number sequence so that the distance function is defined by a special convex function.

This paper considers the problem of finding a largest common subgraph of graphs, which is an important problem in chemical synthesis. It is known that the problem is NP-hard even if graphs are restricted to planar graphs of vertex degree at most three. By the way, a graph is called an almost tree if E(B)V(B)+ K holds for every block B where K is a constant. In this paper, a polynomial time algorithm for finding a largest common subgraph of two graphs which are connected, almost trees and of bounded vertex degree. The algorithm is an extension of a subtree isomorphism algorithm which is based on dynamic programming. Moreover, it is shown that the degree bound is essential. That is, the problem of finding a largest common subgraph of two connected almost trees is proved to be NP-hard for any K0 if degree is not bounded. The three dimensional matching problem, a well known NP-complete problem, is reduced to the problem.