In this paper, we discuss a new property, named dead, of (dataflow) program nets. We say that a node of a program net is dead iff the node cannot fire once in any possible firing sequence, and furthermore the program net is partially dead. We tackle a problem of deciding whether a given program net is partially dead, named dead problem. Program nets can be classified into four subclasses: general, acyclic, SWITCH-less, and acyclic SWITCH-less nets. For each subclass, we give a method of solving dead problem and its computation complexity. Our results show that (i) acyclic SWITCH-less nets are not partially dead; (ii) for SWITCH-less nets, dead problem can be solved in polynomial time; (iii) for acyclic nets and general nets, dead problem is intractable.

We consider a network, where a special data called certificate is issued between two users, and all certificates issued by the users in the network can be represented by a directed graph. For any two users u and v, when u needs to send a message to v securely, v's public-key is needed. The user u can obtain v's public-key using the certificates stored in u and v. We need to disperse the certificates to the users such that when a user wants to send a message to the other user securely, there are enough certificates in them to get the reliable public-key. In this paper, when a certificate graph and a set of communication requests are given, we consider the problem to disperse the certificates among the nodes in the network, such that the communication requests are satisfied and the total number of certificates stored in the nodes is minimized. We formulate this problem as MINIMUM CERTIFICATE DISPERSAL (MCD for short). We show that MCD is NP-Complete, even if its input graph is restricted to a strongly connected graph. We also present a polynomial-time 2-approximation algorithm MinPivot for strongly connected graphs, when the communication requests satisfy some restrictions. We introduce some graph classes for which MinPivot can compute optimal dispersals, such as trees, rings, and some Cartesian products of graphs.

In this paper, we present a hill-shift learning method of the Hopfield neural network for bipartite subgraph problem. The method uses the Hopfield neural network to get a near-maximum bipartite subgraph, and shifts the local minimum of energy function by adjusts the balance between two terms in the energy function to help the network escape from the state of the near-maximum bipartite subgraph to the state of the maximum bipartite subgraph or better one. A large number of instances are simulated to verify the proposed method with the simulation results showing that the solution quality is superior to that of best existing parallel algorithm.

We formally define the mobile agent allocation problem from a system-wide viewpoint and then prove that it is strongly NP-complete even if each agent communicates only with two agents. This is the first formal definition for scheduling mobile agents from the viewpoint of load balancing, which enables us to discuss its properties on a rigorous basis. The problem is recognized as preemptive scheduling with independent tasks that require mutual communication. The result implies that almost all subproblems of mobile agent allocation, which require mutual communication of agents, are strongly NP-complete.

The wavelength-division multiplexing (WDM) technology has been popular in communication societies for providing very large communication bands by multiple lightpaths with different wavelengths on a single optical fiber. Particularly, a double-ring optical network architecture based on the packet-over-WDM technology such as the HORNET architecture, has been extensively studied as a next generation platform for metropolitan area networks (MANs). Each node in this architecture is equipped with a wavelength-fixed optical-drop and a fast tunable transmitter so that a lightpath can be established between any pair of nodes without wavelength conversions. In this paper, we formulate the optical-drop wavelength assignment problem (ODWAP) for efficient wavelength reuse under heterogeneous traffic in this network, and prove the NP-completeness of its decision problem. Then, we propose a simple heuristic algorithm for the basic case of ODWAP. Through extensive simulations, we demonstrate the effectiveness of our approach in reducing waiting times for packet transmissions when a small number of wavelengths are available to retain the network cost for MANs.

This note considers a problem of minimum length scheduling for a set of messages subject to precedence constraints for switching and communication networks, and shows some improvements upon previous results on the problem.

In this paper, introducing a stochastic hill-climbing dynamics into an optimal competitive Hopfield network model (OCHOM), we propose a new algorithm that permits temporary energy increases, which helps the OCHOM escape from local minima. In graph theory, a clique is a completely connected subgraph and the maximum clique problem (MCP) is to find a clique of maximum size of a graph. The MCP is a classic optimization problem in computer science and in graph theory with many real-world applications, and is also known to be NP-complete. Recently, Galan-Marin et al. proposed the OCHOM for the MCP. It can guarantee convergence to a global/local minimum of energy function, and performs better than other competitive neural approaches. However, the OCHOM has no mechanism to escape from local minima. The proposed algorithm introduces stochastic hill-climbing dynamics which helps the OCHOM escape from local minima, and it is applied to the MCP. A number of instances have been simulated to verify the proposed algorithm.

With the explosive growth of the Internet system, demands for broadband communication networks have rapidly increased to provide high quality network services. For this purpose, the IEEE 802.6 MAC standard protocol defines the distributed-queue dual bus (DQDB) for metropolitan area networks (MANs). The isochronous channel reuse problem (ICRP) has been studied for efficient use of DQDB by finding proper channel assignments to incoming connection requests. In this paper, we first define the generalized isochronous channel reuse problem (GICRP) as a generalization of ICRP, to afford demands of simultaneously satisfying plural connection requests such as for multicast applications, where certain sets of connection requests must be assigned channels simultaneously. We prove the NP-completeness of its decision problem. Then, we propose a minimum dead space (MDS) algorithm as a heuristic approach to GICRP. The extensive simulation results show that with shorter computation time, our MDS algorithm can always find better channel assignments reducing the waiting time for packet transmissions than the best existing algorithm for conventional ICRP.

Subgraph isomorphism problems have various important applications, while generally being NP-complete. Though Ullmann and Konishi proposed the custom circuit designs to accelerate subgraph isomorphism problem, they require many hardware resources for large problems. This study describes the design of data-dependent circuits for subgraph isomorphism problem with evaluation results on an actual FPGA platform. Data-dependent circuits are logic circuits specialized in specific input data. Such circuits are smaller and faster than the original circuit, although it is not reusable and involves circuit generation for each input. In the present study, the circuits were implemented on Xilinx XC2V3000 FPGA, and they successfully operated at a clock frequency 25 MHz. In the case of graphs with 16 vertices, the average execution time is about 7.0% of the software executed on an up-to-date microprocessor (Athlon XP 2600+ of 2.1 GHz clock). Even if the circuit generation time is included, data-dependent circuits are about 14.4 times faster than the software (for random graphs with 16 vertices). This performance advantage becomes larger for larger graphs. Two algorithms (Ullmann's and Konishi's) were examined, and the data-dependent approach was found to be equally effective for both algorithms. We also examined two types of input graph sets, and found that the data-dependent approach shows advantage in both cases.

In this paper, we propose a new parallel algorithm for cellular radio channel assignment problem that can help the expanded maximum neural network escape from local minima by introducing a transient chaotic neurodynamics. The goal of the channel assignment problem, which is an NP-complete problem, is to minimize the total interference between the assigned channels needed to satisfy all of the communication needs. The expanded maximum neural model always guarantees a valid solution and greatly reduces search space without a burden on the parameter-tuning. However, the model has a tendency to converge to local minima easily because it is based on the steepest descent method. By adding a negative self-feedback to expanded maximum neural network, we proposed a new parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm then is fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the expanded maximum neural network and the chaotic neurodynamics. Simulations on benchmark problems demonstrate the superior performance of the proposed algorithm over other heuristics and neural network methods.

By using distributed database systems, many advantages can be obtained such as database management cost, efficiency, and high integrity of systems through allocating fragments to many distributed sites with horizontal/vertical fragmentation of global database schema. To minimize costs, distributed algorithms must be applied so that database fragments are allocated to optimal sites. It is useful to replicate fragments, such as allocating many copies in many sites including load balancing. But there are too many possible combinations of each site and fragment, making it impossible to find a solution in real time, i.e., it is an NP-complete problem. This paper proposes near optimal heuristic algorithms for minimizing cost by defining a cost model based on read and update queries that are requested in many sites. Various factors are applied to the proposed algorithms for sizing efficient network resources that compute database transactions as remote query or update requests for consistency in replicated database systems. For network load balancing, incoming network traffic table is defined in each site. A request transaction from unallocated sites to allocated sites can be accessed properly at any other replicated sites by using the network traffic table. Finally, some experimental results verified the proposed algorithms by comparing actual cases of database allocation.

In this paper, based on maximum neural network, we propose a new parallel algorithm that can escape from local minima and has powerful ability of searching the globally optimal or near-optimum solution for the maximum clique problem (MCP). In graph theory a clique is a completely connected subgraph and the MCP is to find a clique of maximum size of a graph. The MCP is a classic optimization problem in computer science and in graph theory with many real-world applications, and is also known to be NP-complete. Lee and Takefuji have presented a very powerful neural approach called maximum neural network for this NP-complete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parameter-tuning. However, the model has a tendency to converge to the local minimum easily because it is based on the steepest descent method. By adding a negative self-feedback to the maximum neural network, we proposed a parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm.

H-coloring problem is a coloring problem with restrictions such that some pairs of colors cannot be used for adjacent vertices, where H is a graph representing the restrictions of colors. We deal with the case that H is the complement graph of a cycle of odd order 2p + 1. This paper presents the following results: (1) chordal graphs and internally maximal planar graphs are -colorable if and only if they are p-colorable (p 2), (2) -coloring problem on planar graphs is NP-complete, and (3) there exists a class that includes infinitely many -colorable but non-3-colorable planar graphs.

A variety of real-time multicast applications such as video conferences, remote lectures, and video-on-demand have become in commonplace with the expansion of broadband Internet services. Due to nontrivial problems in the IP multicast technology, the peer-to-peer multicast technology (P2P-multicast) has emerged as a practical implementation, although its network resource utilization is less efficient. A multihome network has the potential of alleviating this inefficiency by providing flexibility in communication path selections for each host with multiple gateways to the Internet. This paper has first formulated the P2P-multicast routing problem in the multihome network, and has proved the NP-completeness of its decision problem. Then, a two-stage heuristic algorithm called P2PMM_router has been presented for this P2P Multicast Multihome-network routing problem. The first stage constructs an initial multicast routing tree from an optimum spanning tree by Prim algorithm, through satisfying the constraints. The second stage improves the tree by repeating partial modifications and constraint satisfactions. The extensive simulation results using random network instances support the effectiveness of our P2PMM_router.

We present a learning algorithm of the Hopfield neural network for minimizing edge crossings in linear drawings of nonplanar graphs. The proposed algorithm uses the Hopfield neural network to get a local optimal number of edge crossings, and adjusts the balance between terms of the energy function to make the network escape from the local optimal number of edge crossings. The proposed algorithm is tested on a variety of graphs including some "real word" instances of interconnection networks. The proposed learning algorithm is compared with some existing algorithms. The experimental results indicate that the proposed algorithm yields optimal or near-optimal solutions and outperforms the compared algorithms.

Group multicasting is a generalization of multicasting whereby every member of a group is allowed to multicast messages to other members that belongs to the same group. The group multicast routing problem (GMRP) is that of finding a set of multicast trees with bandwidth requirements, each rooted at a member of the group, for multicasting messages to other members of the group. An optimal solution to GMRP is a set of trees, one for each member of the group, that incurs the least overall cost. This problem is known to be NP-complete and hence heuristic algorithms are likely to be the only viable approach for computing near optimal solutions in practice. In this paper, we derive a lower bound on the cost of an optimal solution to GMRP by using Lagrangean Relaxation and Subgradient Optimization. This lower bound is used to evaluate the two existing heuristic algorithms in terms of their ability to find close-to-optimal solutions.

Many application programs can be modeled as a subgraph isomorphism problem. However, this problem is generally NP-complete and difficult to compute. A custom computing circuit is a prospective solution for such problems. This paper examines various accelerator designs for subgraph isomorphism problems based on Ullmann's algorithm and Konishi's algorithm. These designs are quantitatively evaluated from two points of view: logic scale and execution time. Our study revealed that Ullmann's design is faster but larger in logic scale. Partially sequential versions of Ullmann's algorithm can be more cost-effective than Ullmann's original design. The hardware of Konishi's algorithm is smaller in logic scale, operates at a higher frequency, and is more cost-effective.

The Another Solution Problem (ASP) of a problem is the following problem: for a given instance x of and a solution s to it, find a solution to x other than s. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. In this paper we consider n-ASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above. The complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASP-completeness implies NP-completeness, these results can be regarded as new results of NP-completeness proof of puzzles.

Although the subgraph isomorphism problem has various important applications, it is generally NP-complete and difficult to solve. Though a custom computing circuit can reduce the execution time substantially, it requires considerable hardware resources and is inapplicable to large problems. This paper examines the feasibility of data dependent designs, which are particularly suitable to a Field Programmable Gate Array (FPGA). The data dependent approach drastically reduces hardware requirements. For graphs of 32 vertices, the average logic scale of data dependent circuits is only 5% of the corresponding data independent circuit. The data dependent circuit is estimated to be maximally 460 times faster than the software. Even if the circuit generation time is included, a data dependent circuit is estimated to be 2.04 times faster than software for graphs of 32 vertices. The performance gain would increase for larger graphs.

The goal of the maximum cut problem is to partition the vertex set of an undirected graph into two parts in order to maximize the cardinality of the set of edges cut by the partition. The maximum cut problem has many important applications including the design of VLSI circuits and communication networks. Moreover, many optimization problems can be formulated in terms of finding the maximum cut in a network or a graph. In this paper, we propose an improved Hopfield neural network algorithm for efficiently solving the maximum cut problem. A large number of instances have been simulated. The simulation results show that the proposed algorithm is much better than previous works for solving the maximum cut problem in terms of the computation time and the solution quality.