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.

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 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.

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.

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.

The vehicle routing and facility location fields are well-developed areas in management science and operations research application. There is an increasing recognition that effective decision-making in these fields requires the adoption of optimization software that can be embedded into a decision support system. In this paper, we describe the implementation details of our software components for solving the vehicle routing and facility location problems.

In this study, a simple chaos communication system including modulation-demodulation circuits is studied. The influence of modulation-demodulation circuits to chaos synchronization is investigated. For the estimation of communication quality, bit error rate (BER) is calculated by computer simulation when a sequential random pulse information signal is transmitted via this proposed system.

A low-cost technique using commercial UV grade silica fibers to construct microlens array that is suitable for mass-production of long-period gratings is reported. The growth rate of gratings fabricated using these arrays is much faster than the conventional amplitude masks. Our previous work had shown that this technique was 400% more efficient than the metal mask technique. Further improvement of this grating writing technique using plano-convex microlens array is reported in this paper. Under the same writing conditions, long-period gratings with absorption peaks of 1.5 dB and 17 dB were fabricated by using a microlens array and a plano-convex microlens array, respectively.

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.

This letter proposes a congestion control scheme for the ABR service of ATM networks which have non-responding connections. The control scheme is robust with respect to both the round trip delay and the loss of control information caused by non-responding connections. Thus, it is shown that the proposed control scheme guarantees the QoS of the network.

There are no efficient algorithms for almost of all scheduling problems, especially when practical scheduling models are considered. Further there may be none for multi-objective scheduling problems. So we should take efforts to develope efficient approximate algorithms for multi-objective scheduling problems. The main purpose of this paper is to survey approaches to some scheduling problems from the algorithmic view points till now and investigate some hopeful approximate approaches to multiobjective scheduling problems.

This paper demonstrates the slope isn't an appropriate parameter to characterize a signal regarding conducted electromagnetic disturbances. On the other hand, a relevant criterion is made conspicuous: it defines the maximum slope deviation between two segments forming a signal. This criterion is validated by a signal with a maximum slope of 400 mA/µs.

A novel temperature sensor device based on a conventional long-period fiber grating but having an improved sensing resolution is presented. By forming a reflector at one cleaved end of the fiber embedding a long-period grating, a fine interference fringe pattern was obtained within the conventional broadband resonant spectrum of the grating. Due to the fine internal structure of the reflection spectrum of the proposed device, the accuracy in reading the temperature-induced resonant wavelength shift was improved. The formation of the self-interference fringe is analyzed and its properties are discussed in detail. The performance of the proposed device is analyzed by measuring the resonant wavelength shift of the device placed in a hot oven under varying temperature. The rate of the fringe shift is measured to be 551 pm/. The rms deviation is 10 pm over a 100 dynamic range, which corresponds to 0.2 in rms temperature deviation. The thermal variation of the differential effective index of the fiber is calculated to be (0.3 0.1)10-6/ by comparing the analytic calculations with the experimental results. The interference fringe shift is revealed to be inversely proportional to the differential effective group index of the fiber, which implies that the shifting rate strongly depends on the type of fibers and also on the order of the involved cladding mode.

This paper presents a dosimetric analysis in an anatomically realistic human head model for a helical antenna portable telephone by using the finite-difference time-domain (FDTD) method. The head model, developed from magnetic resonance imaging (MRI) data of a Japanese adult head, consists of 530 thousand voxels, of 2 mm dimensions, segmented into 15 tissue types. The helical antenna was modeled as a stack of dipoles and loops with an adequate relative weight, whose validity was confirmed by comparing the calculated near magnetic fields with published measured data. SARs are given both for the spatial peak value in the whole head and the averages in various major organs.

Compact intra-cavity spectroscopic measurements may be obtained with any material that has an absorption signature under the gain bandwidth of a fiber laser. Experiments have demonstrated that compared with a regular absorption scheme, an increase in sensitivity is achieved when using the intra-cavity configuration. The practical limit for this enhancement is given by the fiber laser noise. Since intra-cavity spectroscopy is essentially a single beam technique, the application of dual-beam noise reduction techniques is not possible. However, considering that a single-mode fiber can support two modes of polarization, we have used a polarization beam splitter to create two independent cavities (x and y polarization) with the same noise, one cavity of which contains the absorber. For the first time, this permits the convenient use of Balanced Ratiometric Detection in conjunction with an intra-cavity absorption arrangement.

The robust induced l-norm control problem is considered for uncertain discrete-time systems. We propose a state feedback and an output feedback controller that quadratically stabilize the systems and satisfy a given constraint on the induced l-norm. Both controllers are constructed by solving a set of scalar-dependent linear matrix inequalities (LMI's), and the gain matrices are characterized by the solution to the LMI's.

In this paper, we propose a new secure server-aided RSA secret computation protocol which guards against not only the attacks in [1],[2],[15],[18] but also the new powerful active attacks in [3],[4]. The new protocol is also efficient to support high security level.

This paper describes a fiber-optic level sensor designed to measure the level of liquid propane-butane in a relatively short range (60 cm) in the top part of storage tanks at oil refineries with the purpose of monitoring the level of this product in the filled or slightly underfilled or overfilled tanks during various measuring operations. A discrete multi-element device employing novel refractometric transducers was selected because it yields both a large measurement range and high resolution. Several innovations offer a competitive advantage to industrial users: 1) Special micro-optical refractometric transducer; 2) Efficient and economical sensor multiplexing scheme; 3) Fast level-tracking operational algorithm. The vertical resolution of the sensor -1 cm, the maximum excess pressure in the tank -40 atm (4 MPa). The sensor has the spark-proof and explosion-proof design and optical fiber interface for the transmission of the output data. The sensor successfully measured liquid propane-butane level in storage tanks during numerous cycles of measuring operations.

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 reliable and automatic parameter extraction technique for DFB lasers is developed. The parameter extraction program which is named "LAPAREX" is able to determine many device parameters from a measured sub-threshold spectrum only, including gain- and index-coupling coefficients, and spatial phases of the grating at front and rear facets. Injection current dependence of coupling coefficients in a gain-coupled DFBlaser is observed, for the first time, by making use of it.