Suppose that each arc in a digraph D = (V,A) has two costs of non-negative integers, called a spine cost and a leaf cost. A caterpillar is a directed tree consisting of a single directed path (of spine arcs) and leaf vertices each of which is incident to the directed path by exactly one incoming arc (leaf arc). For a given terminal set K ⊆ V, we study the problem of finding a caterpillar in D such that it contains all terminals in K and its total cost is minimized, where the cost of each arc in the caterpillar depends on whether it is used as a spine arc or a leaf arc. In this paper, we first show that the problem is NP-hard for any fixed constant number of terminals with |K| ≥ 3, while it is solvable in polynomial time for at most two terminals. We also give an inapproximability result for any fixed constant number of terminals with |K| ≥ 3. Finally, we give a linear-time algorithm to solve the problem for digraphs with bounded treewidth, where the treewidth for a digraph D is defined as the one for the underlying graph of D. Our algorithm runs in linear time even if |K| = O(|V|), and the hidden constant factor of the running time is just a single exponential of the treewidth.

A vertex subset I of a graph G is called a k-path vertex cover if every path on k vertices in G contains at least one vertex from I. The K-PATH VERTEX COVER RECONFIGURATION (K-PVCR) problem asks if one can transform one k-path vertex cover into another via a sequence of k-path vertex covers where each intermediate member is obtained from its predecessor by applying a given reconfiguration rule exactly once. We investigate the computational complexity of K-PVCR from the viewpoint of graph classes under the well-known reconfiguration rules: TS, TJ, and TAR. The problem for k=2, known as the VERTEX COVER RECONFIGURATION (VCR) problem, has been well-studied in the literature. We show that certain known hardness results for VCR on different graph classes can be extended for K-PVCR. In particular, we prove a complexity dichotomy for K-PVCR on general graphs: on those whose maximum degree is three (and even planar), the problem is PSPACE-complete, while on those whose maximum degree is two (i.e., paths and cycles), the problem can be solved in polynomial time. Additionally, we also design polynomial-time algorithms for K-PVCR on trees under each of TJ and TAR. Moreover, on paths, cycles, and trees, we describe how one can construct a reconfiguration sequence between two given k-path vertex covers in a yes-instance. In particular, on paths, our constructed reconfiguration sequence is shortest.

We demonstrate the wide-band (> 25-nm) long-distance (> 1000-km) chromatic dispersion compensation by midway spectral inversion (MSI) using a periodically-polled LiNbO3 device. In order to achieve a flat zero net dispersion, the fourth order dispersion of the single-mode fibers is canceled by MSI, while the third order dispersion is compensated for by the negative slope dispersion compensation fiber (NS-DCF). The second order dispersion is canceled out by both. The long distance propagation is realized by a double recirculation-loop system. A very flat zero dispersion is measured for the first time for over 1000-km single-mode fiber propagation with MSI dispersion compensation.

We have developed the tunable dispersion compensator based on two twin linearly chirped fiber Bragg gratings with various temperature gradients. Controlling the temperature gradient over one of the twin fiber Bragg gratings by Peltier elements, the dispersion and the dispersion slope were changed independently and continuously. The dispersion and dispersion slope compensator has a large bandwidth of 8 nm and low group-delay ripple of < 4 ps in its chirped fiber Bragg gratings. We experimentally demonstrated a precise controllability of the dispersion and the dispersion slope using linear and parabolic temperature gradient. The dispersion and the dispersion slope changes were achieved continuously with -0.67 ps/nm/ and -0.14 ps/nm2/. The transmission characteristics of the dispersion slope compensation were examined using ultra short pulses in the fiber link. When the total dispersion was zero, the distorted pulse was restored back and the tail was significantly suppressed. 160 Gbit/s signals were also demonstrated over 140 km within 1 dB power penalty by using the dispersion slope compensator.

This paper describes an on-line Kanji character recognition method that solves the one-to-one stroke correspondence problem with both the stroke-number and stroke-order variations common in cursive Japanese handwriting. We propose two kinds of complementary algorithms: one dissolves excessive mapping and the other dissolves deficient mapping. Their joint use realizes stable optimal stroke correspondence without combinatorial explosion. Also, three kinds of inter-stroke distances are devised to deal with stroke concatenation or splitting and heavy shape distortion. These new ideas greatly improve the stroke matching ability of the selective stroke linkage method reported earlier by the authors. In experiments, only a single reference pattern for each of 2,980 Kanji character categories is generated by using training data composed of 120 patterns written carefully with the correct stroke-number and stroke-order. Recognition tests are made using the training data and two kinds of test data in the square style and in the cursive style written by 36 different people; recognition rates of 99.5%, 97.6%, and 94.1% are obtained, respectively. Moreover, comparative results obtained by the current OCR technique as applied to bitmap patterns of on-line character data are presented. Finally, future work for enhancing the stroke matching approach to cursive Kanji character recognition is discussed.

Given a set P of n points on which facilities can be placed and an integer k, we want to place k facilities on some points so that the minimum distance between facilities is maximized. The problem is called the k-dispersion problem. In this paper, we consider the 3-dispersion problem when P is a set of points on a plane (2-dimensional space). Note that the 2-dispersion problem corresponds to the diameter problem. We give an O(n) time algorithm to solve the 3-dispersion problem in the L∞ metric, and an O(n) time algorithm to solve the 3-dispersion problem in the L1 metric. Also, we give an O(n2 log n) time algorithm to solve the 3-dispersion problem in the L2 metric.

Let G be a graph such that each edge has its list of available colors, and assume that each list is a subset of the common set consisting of k colors. Suppose that we are given two list edge-colorings f0 and fr of G, and asked whether there exists a sequence of list edge-colorings of G between f0 and fr such that each list edge-coloring can be obtained from the previous one by changing a color assignment of exactly one edge. This problem is known to be PSPACE-complete for every integer k ≥ 6 and planar graphs of maximum degree three, but any computational hardness was unknown for the non-list variant in which every edge has the same list of k colors. In this paper, we first improve the known result by proving that, for every integer k ≥ 4, the problem remains PSPACE-complete even for planar graphs of bounded bandwidth and maximum degree three. Since the problem is known to be solvable in polynomial time if k ≤ 3, our result gives a sharp analysis of the complexity status with respect to the number k of colors. We then give the first computational hardness result for the non-list variant: for every integer k ≥ 5, the non-list variant is PSPACE-complete even for planar graphs of bandwidth quadratic in k and maximum degree k.

The energy of a threshold circuit C is defined to be the maximum number of gates outputting ones for an input assignment, where the maximum is taken over all the input assignments. In this paper, we study computational power of threshold circuits of energy at most two. We present several results showing that the computational power of threshold circuits of energy one and the counterpart of energy two are remarkably different. In particular, we give an explicit function which requires an exponential size for threshold circuits of energy one, but is computable by a threshold circuit of size just two and energy two. We also consider MOD functions and Generalized Inner Product functions, and show that these functions also require exponential size for threshold circuits of energy one, but are computable by threshold circuits of substantially less size and energy two.