Assume that each edge e of a graph G is assigned a list (set) L(e) of colors. Then an edge-coloring of G is called an L-edge-coloring if each edge e of G is colored with a color contained in L(e). It is known that any series-parallel simple graph G has an L-edge-coloring if either (i) |L(e)| max{4,d(v),d(w)} for each edge e=vw or (ii) the maximum degree of G is at most three and |L(e)| 3 for each edge e, where d(v) and d(w) are the degrees of the ends v and w of e, respectively. In this paper we give a linear-time algorithm for finding such an L-edge-coloring of a series-parallel graph G.

It is known that all minimum cuts in an edge-weighted undirected graph with n vertices and m edges can be represented by a cactus with O(n) vertices and edges, a connected graph in which each edge is contained in an exactly one cycle. In this paper, we show that such a cactus representation can be computed in O(mn+n2log n) time and O(m) space. This improves the previously best complexity of deterministic cactus construction algorithms, and matches with the time bound of the fastest deterministic algorithm for computing a single minimum cut.

The radiation patterns are synthesized by properly disposing surface variations on dielectric rod waveguides. The genetic algorithm (GA) is applied for searching the optimum disposition of variation sections. A very fast calculation method used in the optimization is presented. The guided waves are related in the form of a 2-port circuit and the radiation field is expressed by superposition of the waves from variation sections. Various conical beams can be synthesized. Short variation sections and combination of several variation sections with different height are used to improve the synthesis performance. The ripple of the mainlobe and the sidelobe levels become small. Spherical sector patterns with a steep fall are synthesized and the agreement with the experimental values is confirmed.

We consider the routing for a multicast in a WDM all-optical network. We prove a min-max theorem on the number of wavelengths necessary for routing a multicast. Based on the min-max theorem, we propose an efficient on-line algorithm for routing a multicast.

In this paper, we propose a novel 2D plenoptic function called "acentric panorama view (APV)." This novel 2D plenoptic function samples the panorama scenes without oversampling or undersampling. A single APV can be accelerated by view culling and list-priority rendering algorithm. Multiple APVs with special fields of view, 45, 60, 90, and 120, can be integrated into a larger configuration called augmented APVs, which can augment the walking area in a planar walkthrough environment to form a 4D plenoptic function. In augmented APVs, the acceleration schemes of a single APV can still be applied successfully.

This letter presents parallel algorithms for matrix multiplication and the fast Fourier transform (FFT) that are significant problems arising in engineering and scientific applications. The proposed algorithms are designed on a 3-dimensional processor array with separable buses (PASb). We show that a PASb consisting of N N h processors can compute matrix multiplication of size N N and the FFT of size N in O(N/h+log N) time, respectively. In order to examine ease of hardware implementation, we also evaluate the VLSI complexity of the algorithms. A result obtained achieves an optimal bound on area-time complexity when h=O(N/log N).

This paper presents a new sliding window algorithm that is well-suited to an elliptic curve defined over an extension field for which the Frobenius map can be computed quickly, e.g., optimal extension field. The algorithm reduces elliptic curve group operations by approximately 15% for scalar multiplications for a practically used curve in compared to Lim-Hwang's results presented at PKC2000, which was the fastest previously reported. The algorithm was implemented on computers. Scalar multiplication can be accomplished in 573 µs, 595 µs, and 254 µs on Pentium II (450 MHz), 21164A (500 MHz), and 21264 (500 MHz) computers, respectively.

This paper describes a rhythm pattern accuracy diagnosis system based on the rhythm pattern matching algorithm and a diagnosis feedback method by employing the SVM technique. A beat rhythm pattern is recorded by a PC and analyzed with an algorithm including cluster-analysis-based pattern matching. Rhythm performance is represented by a performance feature vector, which features note length deviation, note length instability, and tempo instability. The performance feature vector is effective for objectively evaluating the accuracy of rhythm patterns objectively. In addition, this system has the music experts' knowledge base, which is calculated from the performance feature vectors associated with the experts' subjective evaluation by listening to the performance. The system generates both an objective measuring report, and experts' comments for learners. Reproductivity of experts' comments is statistically indicated to be excellent for eight rhythm patterns, two tempo levels, and eight users. Reliability of experts' comments are also described considering the threshold of the decision function of SVM. Subjective evaluation of the system is carried out by fifteen users by a questionnaire using the SD method. As a result of factor analysis for the sixteen questions, four factors named "Audio-visual representation," "User-friendliness," "Reliability," and "Window representation," are extracted. Users' four factor scores indicate that the system is reliable and easy to use.

A digit-recurrence algorithm for computing reciprocal square-root which appears frequently in multimedia and graphics applications is proposed. The reciprocal square-root is computed by iteration of carry-propagation-free additions, shifts, and multiplications by one digit. Different specific versions of the algorithm are possible, depending on the radix, the redundancy factor of the digit set, and etc. Details of a radix-2 version and a radix-4 version and designs of a floating-point reciprocal square-root circuit based on them are shown.

We suggest a new probe message structure and an efficient probe-based deadlock detection and recovery algorithm that can be used in distributed database systems. We determine the characteristics of the probe messages and suggest an algorithm that can reduce the communication cost required for deadlock detection and recovery.

The modern network service of finding the optimal path subject to multiple constraints on performance metrics such as delay, jitter, loss probability, etc. gives rise to the multi-constrained optimal-path (MCOP) QoS routing problem, which is NP-complete. In this paper, this problem is solved through both exact and heuristic algorithms. We propose an exact algorithm E_MCOP, which first constructs an aggregate weight and then uses a K-shortest-path algorithm to find the optimal solution. By means of E_MCOP, the performance of the heuristic algorithm H_MCOP proposed by Korkmaz et al. in a recent work is evaluated. H_MCOP only runs Dijkstra's algorithm (with slight modifications) twice, but it can find feasible paths with a success ratio very close to that of the exact algorithm. However, we notice that in certain cases its feasible solution has an unsatisfactorily high average cost deviation from the corresponding optimal solution. For this reason, we propose some modified algorithms based on H_MCOP that can significantly improve the performance by running Dijkstra's algorithm a few more times. The performance of the exact algorithm and heuristics is investigated through computer simulations on networks of various sizes.

It has been considered difficult to obtain the minimum AND-EXOR expression of a given function with six variables in a practical computing time. In this paper, a faster algorithm of minimizing AND-EXOR expressions is proposed. We believe that our algorithm can compute the minimum AND-EXOR expressions of any six-variable and some seven-variable functions practically. In this paper, we first present a naive algorithm that searches the space of expansions of a given n-variable function f for a minimum expression of f. The space of expansions are generated by using all combinations of (n-1)-variable product terms. Then, how to prune the branches in the search process and how to restrict the search space to obtain the minimum solutions are discussed as the key point of reduction of the computing time. Finally a faster algorithm is constructed by using the methods discussed. Experimental results to demonstrate the effectiveness of these methods are also presented.

In this paper, we analyze the convergence and steady-state behavior of the least mean-square (LMS) adaptive filtering algorithm for a finite-length phase-splitting hybrid-type decision feedback equalizer (H-DFE). With some approximations, we derive an iterative expression for the excess mean-square error (MSE) of the H-DFE, which is composed of three statistically dependent excess MSEs; that is, the excess MSEs of the feedforward filter (FFF), intersymbol interference predictive feedback filter (ISI-FBF), and noise predictive feedback filter (NP-FBF) taps. Computer simulation and analytical results show that the average eigenvalue of the input signal for the NP-FBF taps of the H-DFE is time-varying, whereas those for the FFF and ISI-FBF taps are fixed. Nevertheless, the H-DFE can be implemented with fixed step sizes that ensure the convergence of the LMS algorithm without performance degradation from the standpoint of convergence speed, as well as steady-state performance for digital subscriber line (xDSL) applications.

This paper proposes a new algorithm named WGF (Weight-Gap First) scheduling. It not only supports the maximum throughput of a cell, but also provides the fairness of a terminal in HDR. The WG-based new scheduling algorithm is determined by served data of mobile terminals to guarantee requested data rate. WGs are renewed at each timeslot to improve throughput and fairness. Simulations confirm the better performance of the proposed algorithm in terms of throughput and fairness.

Parallelization of the P-complete problem is known to be difficult. In this paper, we consider the parallelizability of a stack breadth-first search (stack BFS) problem, which is proved to be P-complete. We first propose the longest path length (LPL) as a measure for the P-completeness of the stack BFS. Next, using this measure, we propose an efficient parallel algorithm for the stack BFS. Assuming the size and LPL of an input graph are n and l, respectively, the complexity of the algorithm indicates that the stack BFS is in the class NCk+1 if l = O(logk n), where k is a positive integer. In addition, the algorithm is cost optimal if l=O(nε), where 0 < ε < 1.

In this paper, we propose a medium access control (MAC) protocol for multimedia code division multiple access (CDMA) communications. In the proposed protocol, a base station (BS) estimates the instantaneous number of simultaneously transmitted packets in the future slots with exploiting a stochastic property of traffic. In order to carry out this estimation, we employ an adaptive algorithm. We evaluate the performance of the proposed protocol by comparing that with two different cases. One is no estimation case and the other is perfect estimation case. From these results, we clarify the advantage of the proposed MAC protocol.

The motion estimation can choose the most suitable algorithm for different kinds of motion types, formats, and characteristics. The video encoding system can be optimized for quality, speed, and power consumption. In this paper, we propose a reconfigurable approach to a motion estimation algorithm and hardware architecture. The proposed algorithm determines motion type and then selects adapted block-matching algorithm for different kinds of motion sequences. The quality of our algorithm is better than that of the TSS and the BBGDS algorithm, or comparable to the performance of the better of the two, and the computational complexity of our algorithm is significantly less than that of the TSS. We also propose hardware architecture for realizing two kinds of motion estimations in the same hardware. We implemented the flexible and reconfigurable hardware architecture by using address generator unit, delay unit, and parameters and by using the hardware description language (VHDL) and the SYNOPSYS synthesis design tools. We analyze the performance of the algorithm and present adapted algorithm for a low cost real time application.

This paper describes special-purpose hardware for large-scale logic simulation, called SP2, which executes an event driven algorithm and can simulate up to sixteen million gates. SP2 was developed, in 1992, for system verification of large-scale computer designs as a successor to SP1, which was developed in 1987. SP2 provides enhanced performance, throughput, and delay accuracy over SP1. Since 1992, SP2 has been widely used for system-level simulation of mainframes, super computers, UNIX servers and microprocessors. It is used as a powerful simulator, in all stages of design verification, or in early stages, before regression testing, by using emulators.

The problem of the super-resolution time delay estimation of the real stationary signals is addressed in this paper. The time delay estimation is first converted into a frequency estimation problem. Then a MUSIC-type algorithm to estimate the subsequent frequency from the single-experiment data is proposed, which not only avoids the mathematical model mismatching but also utilizes the advantages of the subspace-based methods. The mean square errors (MSEs) of the time delay estimate of the MUSIC-type method for varying signal-to-noise (SNR) and separation of two received signal components are shown to illustrate that they approximately coincide with the corresponding Cramer-Rao bound (CRB). Finally, the comparison between the MUSIC-type method and the other conventional methods is presented to show the advantages of the proposed method in this paper.

Recursive least absolute(RLA) error algorithm is derived which is basically the sign algorithm (SA) combined with recursive estimation of the inverse covariance matrix of the reference input. The name RLA comes from the absolute error criterion. Analysis of the transient behavior and steady-state performance of the RLA algorithm is fully developed. Results of experiment show that the RLA algorithm considerably improves the convergence rate of the SA while preserving the robustness against impulse noise. Good agreement between the simulation and the theoretically calculated convergence validates the analysis.