The two dimensional mesh is widely considered to be a promising parallel architecture in its scalability. In this architecture, processors are naturally placed at intersections of horizontal and vertical grids, while there can be three different types of communication links: (i) The first type is the most popular model, called a mesh-connected computer: Each processor is connected to its four neighbours by local connections. (ii) Each processor of the second type is connected to a couple of (row and column) buses. The system is then called a mesh of buses. (iii) The third model is equipped with both buses and local connections, which is called a mesh-connected computer with buses. Mesh routing has received considerable attention for the last two decades, and a variety of algorithms have been proposed. This paper provides an overview of lower and upper bounds for algorithms, with pointers to the literature, and suggests further research directions for mesh routing.

In this paper, a puzzle called Cell-Maze is analyzed. In this puzzle, cells are arranged in checker board squares. Each cell is rotated when a player arrives at the cell. Cell-Maze asks whether or not a player started from a start cell can reach a goal cell. The reachability problem for ordinary graphs can be easily solved in linear time, however a reachability problem for the network such as Cell-Maze may be extremely difficult. In this paper, NP-hardness of this puzzle is proved. It is proved by reducing Hamiltonian Circuit Problem of directed planar graph G such that each vertex involved in just three arcs. Furthermore, we consider subproblems, which can be solved in polynomial time.

Given a combinatorial problem on a set of weighted elements, if we change the weight using a parameter, we obtain a parametric version of the problem, which is often used as a tool for solving mathematical programming problems. One interesting question is how to describe and analyze the trajectory of the solution. If we consider the trajectory of each weight function as a curve in a plane, we have a set of curves from the problem instance. The curves induces a cell complex called an arrangement, which is a popular research target in computational geometry. Especially, for the parametric version of the problem of computing the minimum weight base of a matroid or polymatroid, the trajectory of the solution becomes a subcomplex in an arrangement. We introduce the interaction between the two research areas, combinatorial optimization and computational geometry, through this bridge.

A correlation-based technique for measuring Brillouin gain spectrum distribution along an optical fiber is proposed, which employs frequency-modulated pump and probe lightwaves. The spatial-resolution of about 40 cm is demonstrated, which cannot be realized by the conventional pulse-based technique.

Attempts have been made to evaluate and investigate the radiated emissions from fiber optical modules that are currently available in the market. Far electric field strength measurements show that the radiated emission has a peak at a high-order harmonic wave of the fundamental pulse frequency and reaches a level exceeding the limiting values of the CISPR noise specifications. Near magnetic field distribution measurements show that the source of the interference noise lies between a light emitting diode (LED) module and an LED driver. These measurements are compared with those of electromagnetic field calculations based on a high-frequency equivalent circuit. As a result, it was established that both the peaking effects of deformed pulse waves transmitted between an LED module and an LED driver and the radiation characteristics of the optical transmitter circuit act as factors for increasing the radiation level of the peak frequencies in the radiated emission from fiber optical modules.

The linear complementarity problem (LCP) is one of the most widely studied mathematical programming problems. The theory of LCP can be extended to oriented matroids which are combinatorial abstractions of linear subspaces of Euclidean spaces. This paper briefly surveys the LCP, oriented matroids and algorithms for the LCP on oriented matroids.

This paper presents the switching control and VLSI architecture for the AAL2 switch. The ATM network with the AAL2 switch can efficiently transmit low-bit-rate data, even if the network has many endpoints. The switch is capable of not only switching AAL2 cells but also converting the header of other types of ATMs. The AAL2 switch is integrated into a single chip. The proposed ATM network is constructed by AAL2 switches attached to the ATM switches.

It is an important problem in signal processing, system realization and system identification to find linear discrete-time systems which are consistent with given covariance parameters. This problem is formulated as a problem of finding discrete-time positive real functions which interpolate given covariance parameters. Among various solutions to the problem, a recent remarkable one is a parameterization of all the discrete-time strictly positive real functions that interpolate the covariance parameters and have a limited McMillan degree. In this paper, we use more general input-output characteristics than covariance parameters and consider finding discrete-time positive real functions which interpolate such characteristics. The input-output characteristics are given by the coefficients of the Taylor series at some complex points in the open unit disk. Based on our previous work, we present an algorithm to generate all the discrete-time positive real functions that interpolate the input-output characteristics and have a limited McMillan degree. The algorithm is more general and simpler than the previous one, and is an important practical supplement to the previous work. Moreover, the interpolation of the general input-output characteristics can be effectively applied to the frequency-weighted model reduction. Hence, the algorithm makes a contribution to the problem from the practical viewpoint as well as the theoretical viewpoint.

Graph coloring is a fundamental problem, which often appears in various scheduling problems like the file transfer problem on computer networks. In this paper, we survey recent advances and results on the edge-coloring, the f-coloring, the [g,f]-coloring, and the total coloring problem for various classes of graphs such as bipartite graphs, series-parallel graphs, planar graphs, and graphs having fixed degeneracy, tree-width, genus, arboricity, unicyclic index or thickness. In particular, we review various upper bounds on the minimum numbers of colors required to color these classes of graphs, and present efficient sequential and parallel algorithms to find colorings of graphs with these numbers of colors.

Signal conservation logic (SCL) is a model of logic for the physical world subject to the matter conservation law. This letter proves that replication, complementary replication, and computational universality called elemental universality are equivalent in SCL. Since intelligence has a close relation to computational universality, the presented theorem may mean that life under the matter conservation law eventually acquires some kind of intelligence.

In this paper, we consider the static multiprocessor scheduling problem for a class of multiprocessor systems consisting of m ( 1) identical processors connected by a complete network. The objective of this survey is to give a panoramic view of theoretical and/or practical approaches for solving the problem, that have been extensively conducted during the past three decades.

A novel technique has been developed for in situ sensing of thin film growth. In this method, a fiber optic probe is placed at an appropriate position in a deposition chamber, and the thin film builds up on the end of the fiber. This film is either the same as on the wafer where deposition occurs, or it bears a fixed relationship to the film on the wafer. By an analysis of the intensity of the light reflected from the film and guided by the fiber, information on the film may be obtained. With interference causing maxima, minima and a point of inflection as the film grows, it is possible to obtain near real time information on the following quantities: the real and imaginary parts of the refractive index of the film, a Gaussian parameter characterizing surface roughness, and the film thickness itself. To demonstrate this technique, we have studied the deposition of silicon nitride films in a CVD reactor and how reactor temperature and reactant flow rates influence film growth. This technique may be applied to measure in situ reflectivity of multi layer films, so that reflectance as a function of temperature and time may be obtained. Because the measurement is simple and direct and the information is optical, we believe that this technique has the potential to supplant quartz oscillators in the measurement of thin film growth.

In this paper, we will report on a fiber optic oxygen sensor using fluorescence and its application to clinical examinations. It is based on fluorescence quenching. The quenching ratio of fluorescence is proportional to oxygen partial pressure by Stern-Volmer's formula in which oxygen concentration is estimated from measured emission intensity. We fabricated a microscopic luminous probe using a Solvent Green 5 doped plastic optical fiber coupler. The probes were demonstrated to have certain advantages for example they can be operated in both liquid and gas phases. And also, they are stable to pH and flow velocities. As a clinical application, the probe can reliably measure oxygen concentrations of whole blood in vivo. Moreover, we have clarified various characteristics of this probe.

A convex hull is one of the most fundamental and interesting geometric constructs in computational geometry. Considerable research effort has focused on developing algorithms, both in serial and in parallel, for computing convex hulls. In particular, there are few problems whose parallel algorithms are so thoroughly studied as convex hull problems. In this paper, we review the convex hull parallel algorithms and their paradigm. We provide a summary of results and introduce several interesting topics including typical techniques, output-size sensitive methods, randomized approaches, and robust algorithms for convex hull problems, with which we may see the highlights of the whole research for parallel algorithms. Most of our discussion uses the PRAM (Parallel Random Access Machine) computational model, but still we give a glance at the results of the other parallel computational models such as mesh, mesh-of-trees, hypercube, recofigurable array, and models of coarse grained multicomputers like BSP and LogP.

The main problem considered is submodular set cover, the problem of minimizing a linear function under a nondecreasing submodular constraint, which generalizes both well-known set cover and minimum matroid base problems. The problem is NP-hard, and two natural greedy heuristics are introduced along with analysis of their performance. As applications of these heuristics we consider various special cases of submodular set cover, including partial cover variants of set cover and vertex cover, and node-deletion problems for hereditary and matroidal properties. An approximation bound derived for each of them is either matching or generalizing the best existing bounds.

The legal firing sequence problem (LFS) asks if it is possible to fire each transition some prescribed number of times in a given Petri net. It is a fundamental problem in Petri net theory as it appears as a subproblem, or as a simplified version of marking reachability, minimum initial resource allocation, liveness, and some scheduling problems. It is also known to be NP-hard, however, even under various restrictions on nets (and on firing counts), and no efficient algorithm has been previously reported for any class of nets having general edge weights. We show in this paper that LFS can be solved in polynomial time (in O(n log n) time) for a subclass of state machines, called cacti, with arbitrary edge weights allowed (if each transition is asked to be fired exactly once).

The pseudo-lattice method has been developed for dynamic 3-D liquid-crystal director simulation in thin-film-transistor liquid-crystal displays. Its feature is that the equation of motion of the director is not formularized from the real-lattices, but from the pseudo-lattices organized between the real-lattices. The director on the pseudo-lattice is calculated from the real-lattices by insertion. The objective is to simulate the continuous nematic symmetry correctly and to reduce time and memory needed for the calculation. Especially in this paper, the pseudo-lattice method is explained in detail. Moreover, experiments have been done, and the simulated behavior and location of the bright line, which is caused by the distortion of the director profile, were confirmed to be the same as the actual ones. In particular, the movement and elimination process of the bright line were simulated for the first time.

We survey recent developments in the study of approximation algorithms for NP-hard geometric optimization problems. We focus on those problems which, given a set of points, ask for a graph of a specified type on those points with the minimum total edge length, such as the traveling salesman problem, the Steiner minimum tree problem, and the k-minimum spanning tree problem. In a recent few years, several polynomial time approximation schemes are discovered for these problems. All of them are dynamic programming algorithms based on some geometric theorems that assert the existence of a good approximate solution with a simple recursive decomposition structure. Our emphasis is on these geometric theorems, which have potential uses in the design and analysis of heuristic algorithms.

An epoxy-modified urethane rubber mixed with carbon particles is now chosen as the millimeter-wave absorber material in our study. The absorption characteristics of the absorber is measured under temperature changes. The weatherability of our absorber is also clarified based on absorption characteristics, thickness and hardness of the sample. As a result of the temperature characteristics of the absorber, the difference of the maximum absorption frequency under temperature changes is about 1 GHz, however the absorption of 20 dB or more is obtained between 54 and 58 GHz. The result of accelerated artificial exposure test is that 2.8% of the thickness of our sample is shrunk after 1000 hour exposure, and the hardness of rubber is hardened with increasing test time. It is also confirmed that the deterioration of the absorption ranges from 1 to 3 dB, although the absorption of about 20 dB is kept at the frequency range. As a consequence, it is confirmed that the wave absorber using the epoxy-modified urethane rubber mixed with carbon particles has good weatherability including our desired temperature characteristics, and it is suitable for outdoor use.

This paper surveys two methods for designing numerically robust geometric algorithms. The first method is the exact-arithmetic method, in which numerical computations are done in sufficiently high precision so that all the topological judgements can be done correctly. This method is usually accompanied with lazy evaluation and symbolic perturbation in order to reduce the computational cost and the implementation cost. The second method is the topology-oriented method, in which the consistency of the topological structure is considered as higher-priority information than numerical computation, and thus inconsistency is avoided. Both of the methods are described with the implementation examples.