In wavelength-division multiplexed wide-area optical networks, erbium-doped fiber amplifiers (EDFAs) are usually employed to boost lightwave power. However, EDFAs can only cover 35 nm of the 200 nm fiber bandwidth at 1.55 /spl mu/m, and therefore messages transmitted on the remaining fiber bandwidth cannot be amplified. The authors propose to use wavelengths outside the EDFA bandwidth for sending messages over short distances in which amplification is not necessary. Routing determines which wavelength and links a message is routed on, and hence whether or not a message needs amplification. The authors design static and dynamic routing algorithms in circuit-switched networks and analyze the performance using simulation. The results show that use of wavelengths outside the EDFA bandwidth can decrease blocking and increase the network capacity.>

Rerouting for a circuit-switched wavelength-division-multiplexed all-optical network is considered in the paper. Due to the wavelength continuity constraint, a new connection may be blocked even if bandwidth is available between the origin and the destination. Rerouting can make the available bandwidth wavelength-continuous by changing the routes of certain existing connections to accommodate the new connection. To avoid disruptions of existing connections, move-to-vacant wavelength-retuning (MTV WR) is proposed as the basic operation of circuit migration, in which a circuit is moved to a vacant wavelength on the same path, and the parallel MTV WR rerouting scheme is considered to reroute multiple circuits on disjoint sets of links. The authors design the optimal algorithm which minimizes the weighted number of rerouted circuits with the parallel MTV WR rerouting scheme. Numerical results using simulation show that rerouting can effectively reduce the blocking probability due to the wavelength continuity constraint while minimizing the incurred disruptions.>

A wavelength-convertible switch architecture and routing algorithm for circuit-switched wavelength-division-multiplexing optical networks is studied. Wavelength converters are used to resolve wavelength conflicts and to reuse wavelengths. These converters are not dedicated to individual channels, but are shared by the channels of a node or those of an outbound link in the share-per-node or the share-per-link wavelength-convertible switch, respectively. A routing algorithm is developed to converse wavelength converters while maintaining performance close to that of a network with abundant converters. It is found that converters can improve the network performance, such as the blocking probability and fairness, considerably.>

The performances of seven neural network models for traffic control problems in multistage interconnection networks are compared. The decay term, three neuron models, and two heuristics were evaluated. The goal of the traffic control problems is to find conflict-free switching configurations with the maximum throughput. The simulation results show that the hysteresis McCullock-Pitts neuron model without the decay term and with two heuristics has the best performance.>

The authors propose the first parallel improvement algorithm using the maximum neural network model for the bipartite subgraph problem. The goal of this NP-complete problem is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that the algorithm finds a solution within 200 iteration steps and the solution quality is superior to that of the best existing algorithm. The algorithm is extended for the K-partite subgraph problem where no algorithm has been proposed.

A new parallel processing algorithm for solving string search problems is presented. The proposed algorithm uses O(m*n) processors where n is the length of a text and m is the length of a pattern. It requires two and only two iteration steps to find the pattern in the text, while the best existing parallel algorithm needs the computation time O(loglog n).>

For the original article see ibid., vol.8, no.3, p.257-67 (1989). The commenters point out that their parallel algorithm provides the maximum planar subgraph, and they compare it to the maximal planar subgraph provided by R. Jayakumar et al. in the above-mentioned paper. The space-time product complexity is also compared.>

The authors refers to the work of Y. Takefuji et al. (see ibid., vol.1, pp. 263-267, Sept. (1990)), which is concerned with the problem of RNA secondary structure prediction, and draws the reader's attention to his own model and experiments in training the neural networks on small tRNA subsequences. The author admits that Takefuji et al. outline an elegant way to map the problem onto neural architectures, but suggests that such mappings can be augmented with empirical knowledge (e.g., free energy values of base pairs and substructures) and the ability to learn. In their reply, Y. Takefuji and K.-C. Lee hold that the necessity of the learning capability for the RNA secondary structure prediction is questionable. They believe that the task is to build a robust parallel algorithm considering more thermodynamic properties in the model.

A parallel algorithm for finding a near-maximum independent set in a circle graph is presented. An independent set in a graph is a set of vertices, no two of which are adjacent. A maximum independent set is an independent set whose cardinality is the largest among all independent sets of a graph. The algorithm is modified for predicting the secondary structure in ribonucleic acids (RNA). The proposed system, composed of an n neural network array (where n is the number of edges in the circle graph of the number of possible base pairs), not only generates a near-maximum independent set but also predicts the secondary structure of ribonucleic acids within several hundred iteration steps. The simulator discovered several solutions which are more stable structures, in a sequence of 359 bases from the potato spindle tuber viroid, than previously proposed structures.

A parallel algorithm for tiling with polyominoes is presented. The tiling problem is to pack polyominoes in a finite checkerboard. The algorithm using lxmxn processing elements requires O(1) time, where l is the number of different kinds of polyominoes on an mxn checkerboard. The algorithm can be used for placement of components or cells in a very large-scale integrated circuit (VLSI) chip, designing and compacting printed circuit boards, and solving a variety of two- or three-dimensional packing problems.