Many combinatorial problems can be efficiently solved for partial k-trees (graphs of treewidth bounded by k). The edge-coloring problem is one of the well-known combinatorial problems for which no NC algorithms have been obtained for partial k-trees. This paper gives an optimal and first NC parallel algorithm to find an edge-coloring of any given partial k-tree with bounded degrees using a minimum number of colors. In the paper k is assumed to be bounded.

As a first step to develop a system to analyze or recognize patterns contained in mages, it is important to provide a good base representation that can facilitate efficiently the interpretation of such patterns. Since structural features of basic patterns in document images such as characters or tables are horizontal and vertical stroke components, we propose a new expression of document image based on the MCR expression that can express well such features of text and tabular components of an image.

A Hierarchical Cubic Network (HCN) is a hierarchical hypercube network proposed by Ghose. The HCN is topologically superior to many other similar networks, in particular, the hypercube. It has a considerably lower diameter than a comparable hypercube and is realized using almost half the number of links per node as a comparable hypercube. In this paper, we propose the shortest routing algorithm in HCN(n, n) and show that the diameter of HCN(n, n) with 22n nodes is n(n1)/31 which is about 2/3 of that of a comparable hypercube. We also propose the optimal routing algorithm in HCN(m, n) where mn and obtain that its diameter is n(m1)/31. Typical parallel algorithms run in HCN(m, n) with the same time complexity as a hypercube and the hypercube topology can be emulated with O(1) time complexity in it.

In this paper, we report a new approach about parsing and searching problem for a given phonetic lattice. The approach is based on the Divide and Conquer (DC) strategy. By dividing the phonetic lattice, we first construct a PD-tree to represent this lattice, then, we parse through this PD-tree to identify the possible sentence which is supposed to be the speech utterance. Next, we propose a new search scheme called Downward Request (DR) search model to decrease the computation costs, and this search model gives us the optimal or N-best solutions. Experiments performed on Chinese speech recognition show us the good results.

This paper deals with an efficient radix-2 divider design theory that uses carry-propagation-free adders based on redundant binary{1, 0, 1} representation. In order to compute the division fast, we look ahead to the next step quotient-digit selection embedded in the current partial remainder calculation. The solution is a function of the four most significant digits of the current partial remainder, when scaling the divisor in the range [1, 9/8). In gate depth, this result is better than the higher radix-4 case without the look-ahead quotient-digit selection and the design is simple.

A self-induced-transparent (SIT) system that takes advantage of morphology dependent resonances (MDR's) in a Mie-sized microsphere doped with a resonant material is proposed. The present system is doubly resonant: one has microscopic origin (the two-level system), while the other has macroscopic origin (the MDR). In this geometry, owing to the feedback action of MDR's, the pulse area can be much expanded, and thus the electric-field amplitude of the incident pulse can be reduced substantially compared with the conventional one-way SIT propagation. Theoretical results that incorporate dephasing due to structural imperfections are shown.

Some CMOS gates are topologically asymmetric in inputs, even though they are logically symmetric. It implies a possibility to reduce power consumption by optimizing signal assignment to the inputs. In this study we theoretically derive power consumption of 2-input NAND gate based on transition probability of input signals, with taking into account charging current due to an internal node. We also propose a signal assignment method to input terminals for reducing power consumption reduction by extending our method for large circuits, and demonstrate the effect of power consumption reduction by the present method.

A graph G is said to be universal for a family F of graphs if G contains every graph in F as a subgraph. A minimum universal graph for F is a universal graph for F with the minimum number of edges. This paper considers a minimum universal graph for the family Fkn of graphs on n vertices with path-width at most k. We first show that the number of edges in a universal graph Fkn is at least Ω(kn log(n/k)). Next, we construct a universal graph for Fkn with O(kn log(n/k)) edges, and show that the number of edges in a minimum universal graph for Fkn is Θ(kn log(n/k)) .

A number of flexible control mechanisms used in buffer management, congestion control and bandwidth allocation have been proposed to improve the performance of ATM networks by introducing parameters, such as threshold, push-out probability and incremental bandwidth size of a virtual path, which are adjustable by network providers. However, it is difficult to adaptively adjust these parameters, since the traffic in ATM networks is further complicated by accommodating various kinds of services. To overcome the problem, we propose in this paper a control scheme based on the genetic algorithms and the neural estimator. The neural estimator forecasts the future QOS values for each candidate parameter set, and the genetic algorithms select the best one to control the real network. An example of buffer management in an ATM switch is examined in this paper. Simulation results show the effectiveness of the proposed control scheme in adaptively adjusting the parameter set even when the traffic environment and the QOS requirements are dynamically changing.

A parallel overlapping preconditioner is applied to ICCG method and the effect of the parallel preconditioning on the convergence of the method is investigated by solving large scale block tridiagonal linear systems arising from the discretization of Poisson's equation. Compared with the original ICCG method, the parallel preconditioned ICCG method can solve the problems in high parallelism with slight increasing the number of iterations. Furthermore, the speedup and the efficiency are evaluated for the parallel preconditioned ICCG method by substituting the experimental results into formulae of complexity. For example, when a domain of simulation is discretized on a 250250 rectangular grid and the preconditioner is divided into 249 smaller ones, its speedup is 146.3 with the efficiency 0.59.

We give an efficient shortest path algorithm on a mesh-connected processor array for nn banded matrices with bandwidth b. We use a b/2b/2 semisystolic processor array. The input data is supplied to the processor array from the host computer. The output from the processor array can be also supplied to itself through the host computer. This algorithm computes all pair shortest distances within the band in 7n4b/21 steps.

We developed an eye-contact technique using a blazed half-transparent mirror (BHM), which is a micro-HM array arranged on the display surface, to make a compact eye-contact videophone. This paper describes a new BHM structure that eliminates ghosts and improves image quality. In the new BHM, the reflection and transmission areas are separated to exclude ghosts from appearing in the captured image. We evaluated the characteristics of the captured and displayed images. The results show that the contrast ratio of the captured image and the brightness of both captured and displayed images are much better than with the previous BHM.

This paper investigates the problem of scheduling parallel tasks" with consideration of communication cost on an m-processor system, where processors are assumed to be identical and tasks being scheduled are independent such that they can run on more than one processor simultaneously. Once a task is processed in parallel, its finish time will be speeded up, but communication cost will also be incurred and should be taken into account. To find a schedule with minimum finish time for the parallel tasks scheduling problem is NP-hard. Therefore, in this paper, we will propose a heuristic algorithm for this kind of problem and derive its performance bounds for two different cases of applications, respectively.

Connection Admission Control (CAC) is a key part of traffic control and still leaves several challenging problems peculiar to ATM networks. One of these problems is how to assign sufficient bandwidth for any cell arrival process that satisfies the source traffic descriptor values specified by negotiation between the network and a user at the connection setup. Because the source traffic descriptor cannot describe the actual source traffic characteristics completely, it has already been studied extensively that how to estimate sufficient bandwidth under the assumption that the actual traffic parameter values in the source traffic descriptor are equal to the negotiated values. This paper extends the studies in the literature to how to estimate sufficient bandwidth only assuming that the actual values satisfy the negotiated values, that is the actual values is less than or equal to the negotiated values. We show the sufficient condition for negotiated source traffic descriptors ensuring that the cell-loss ratio calculated from the negotiated values is always the upper-bound of the actual cell-loss ratio. Using this condition, we propose a CAC that can guarantee cell-loss ratio objective so far as a user satisfies the source traffic descriptor values.

The design procedure of a multithreaded processor dedicated to the image generation is described, which can be achieved by means of a high-level synthesis tool PARTHENON. The processor employs a multithreaded architecture which is a novel promising approach to the parallel image generation. This paper puts special stress on the high-level synthesis scheme which can simplify the behavioral description for the structure and control of a complex hardware, and therefore enables the design of a complicated mechanism for a multithreaded processor. Implementation results of the synthesis are also shown to demonstrate the performance of the designed processor. This processor greatly improves the throughput of the image generation so far attained by the conventional approach.

In this paper we describe the formal conditions to detect and resolve all kinds of pipeline data hazards and propose a scheduling algorithm for pipelined instruction set processor synthesis. The algorithm deals with multi cycle operations and tries to minimize the pipeline execution cycles under a given hardware configuration with/without hardware interlock. The main feature that makes the proposed algorithm different from existing ones is the algorithm is for estimating the performance in HW/SW partitioning, with capability of handling a module library of different FUs and dealing with multi cycle operations to be implemented in software. Experimental results of application to ASIP HW/SW codesign show that the proposed algorithm is effective and considerable pipeline execution cycle reduction rates can be achieved. The time complexity of the scheduing algorithm is of O(n2) in the worst case, where n is the number of instructions in a given basic block.

We define a new framework for rewriting graphs, called a formal graph system (FGS), which is a logic program having hypergraphs instead of terms in first-order logic. We first prove that a class of graphs is generated by a hyperedge replacement grammar if and only if it is defined by an FGS of a special form called a regular FGS. In the same way as logic programs, we can define a refutation tree for an FGS. The classes of TTSP graphs and outerplanar graphs are definable by regular FGSs. Then, we consider the problem of constructing a refutation tree of a graph for these FGSs. For the FGS defining TTSP graphs, we present a refutation tree algorithm of O(log2nlogm) time with O(nm) processors on an EREW PRAM. For the FGS defining outerplanar graphs, we show that the refutation tree problem can be solved in O(log2n) time with O(nm) processors on an EREW PRAM. Here, n and m are the numbers of vertices and edges of an input graph, respectively.

An efficient algorithm is given for finding all solutions of piecewise-linear resistive circuits containing nonseparable transistor models such as the Gummel-Poon model or the Shichman-Hodges model. The proposed algorithm is simple and can be easily programmed using recursive functions.

An efficient algorithm is presented for finding all solutions of piecewise-linear resistive circuits containing sophisticated transistor models such as the Gummel-Poon model or the Shichman-Hodges model. When a circuit contains these nonseparable models, the hybrid equation describing the circuit takes a special structure termed pairwise-separability (or tuplewise-separability). This structure is effectively exploited in the new algorithm. A numerical example is given, and it is shown that all solutions are computed very rapidly.

A simple method is presented to calculate the parasitic capacitance effect in the propagation delay of series-connected MOS (SCM) structures. This method divides SCM circuits into two parts and accurately calculates the contribution of each part to the difference from the delay without parasitic capacitances.