In this paper, we give an algorithm for the node-to-set disjoint paths problem in a transposition graph. The algorithm is of polynomial order of n for an n-transposition graph. It is based on recursion and divided into two cases according to the distribution of destination nodes. The maximum length of each path and the time complexity of the algorithm are estimated theoretically to be O(n7) and 3n - 5, respectively, and the average performance is evaluated based on computer experiments.

This paper deals with the Optimum Communication Spanning Tree Problem (OCST) which is well known as an NP-hard problem. For solving the problem, we uses an evolutionary approach. This paper presents a new effective tree encoding and proposes a tree construction routine (TCR) to generate a tree from the encoding. The basic principle is to break a cycle. We also propose a new crossover operator that focuses on the inheritance of parental information and the use of network information. Consequently, we confirm that the proposed algorithm is superior to other algorithms applied to the OCST problem or other tree problems. Moreover, our method can find a better solution than the solution which was previously known as the best solution. In addition, we analyzed the locality and diversity property of encoding and observed that the proposed method has high locality and at the same time it preserves population diversity for many generations. Finally, we conclude that these properties are the main reasons why the proposed method outperforms the other encodings.

A hardware algorithm for integer division is proposed. It is based on the radix-2 non-restoring division algorithm. Fast computation is achieved by the use of the radix-2 signed-digit (SD2) representation. The algorithm does not require normalization of the divisor, and hence, does not require an area-consuming leading-one (or zero) detection nor shifts of variable-amount. Combinational (unfolded) implementation of the algorithm yields a regularly structured array divider, and sequential implementation yields compact dividers.

Scheduling algorithms are playing a key role in overall system performance of broadband wireless systems (BWS). Maximal SNR (MaxSNR) and Round Robin (RR) are two conventional scheduling strategies which emphasize efficiency and fairness respectively. Proportional Fair (PF) algorithm provides tradeoff between efficiency and fairness. In this paper, we apply PF to IEEE 802.16a OFDM based BWS and name it OPF. We also propose a new algorithm for multimedia services: Normalized Multimedia Adaptive OPF (NMAOPF). Adaptive modulation and coding scheme is applied in time varying and frequency selective fading wireless channel. System performances are compared in efficiency and fairness with and without user mobility. Efficiency is in terms of throughput, mean packet delay and packet drop ratio; fairness is in terms of user satisfaction rate and average user rate. Joint PHY and MAC layer simulation results show that: within the traffic range of 55 to 70 Mbps, compared with RR and MaxSNR, the performance of OPF is in between. Our proposed NMAOPF outperforms all others without user mobility, while under mobility, it is not as good as MaxSNR but better than OPF and RR.

This paper proposes efficient DSP instructions and their hardware architecture for the Viterbi algorithm. The implementation of the Viterbi algorithm on a DSP chip has been attracting more interest for its flexibility, programmability, etc. The proposed architecture can reduce the Trace Back (TB) latency and can support various wireless communication standards. The proposed instructions perform the Add Compare Select (ACS) and TB operations in parallel and the architecture has special hardware, called the Offset Calculation Unit (OCU), which automatically calculates data addresses for acceleration of the trellis butterfly computations. When the constraint length K is 5, the proposed architecture can reduce the decoding cycles about 17% compared with Carmel DSP and about 45% compared with TMS320C55x.

The global Lanczos algorithm for solving the RLCG interconnect circuits is presented in this paper. This algorithm is an extension of the standard Lanczos algorithm for multiple-inputs multiple-outputs (MIMO) systems. A new matrix Krylov subspace will be developed first. By employing the congruence transformation with the matrix Krylov subspace, the two-side oblique projection-based method can be used to construct a reduced-order system. It will be shown that the system moments are still matched. The error of the 2q-th order system moment will be derived analytically. Furthermore, two novel model-order reduction techniques called the multiple point global Lanczos (MPGL) method and the adaptive-order global Lanczos (AOGL) method which are both based on the multiple point moment matching are proposed. The frequency responses using the multiple point moment matching method have higher coherence to the original system than those using the single point expansion method. Finally, simulation results on frequency domain will illustrate the feasibility and the efficiency of the proposed methods.

In this paper, we propose a new multiuser detection scheme using Maximum Likelihood (ML) criterion and the M algorithm for Multi Carrier (MC)-Code Division Multiple Access (CDMA) systems in the down-link channel. We first describe an implementation of ML detection separating In- and Quadrature-phase components and using well-known linear filters. In the proposed algorithm, we produce hypothesis symbol vectors in a tree structure by partly changing the sub-optimum hard decisions based on the linear filter output. At each stage, we adopt the best M likely paths with respect to the true log likelihood or distance function as survivors. We determine the symbol vector which minimizes the distance function at the final stage. Although the complexity of ML detector is exponentially increasing as a function of the number of users, the proposed scheme requires by far less complexity. We demonstrate that the proposed scheme achieves equivalent Bit Error Rate (BER) performance with lower complexity in comparison with ML detector by computer simulations. Moreover we compare the proposed detection scheme with QRD-M algorithm which is based on QR decomposition combined with M algorithm.

Design of optimal controllers satisfying performance criteria of minimum tracking error and disturbance level for an interval system using a multi-objective evolutionary approach is proposed in this paper. Based on a worst-case design philosophy, the design problem is formulated as a minimax optimization problem, subsequently solved by a proposed two-phase multi-objective genetic algorithm (MOGA). By using two sets of interactive genetic algorithms where the first one determines the maximum (worst-case) cost function values for a given set of controller parameters while the other one minimizes the maximum cost function values passed from the first genetic algorithm, the proposed approach evolutionarily derives the optimal controllers for the interval system. To suitably assess chromosomes for their fitness in a population, root locations of the 32 generalized Kharitonov polynomials will be used to establish a constraints handling mechanism, based on which a fitness function can be constructed for effective evaluation of the chromosomes. Because of the time-consuming process that genetic algorithms generally exhibit, particularly the problem nature of minimax optimization, a parallel computation scheme for the evolutionary approach in the MATLAB-based working environment is also proposed to accelerate the design process.

The Schaub bound is one of well-known lower bounds of the minimum distance for given cyclic code C, and defined as the minimum value, which is a lower bound on rank of matrix corresponding a codeword, in defining sequence for all sub-cyclic codes of given code C. In this paper, we will try to show relationships between the Schaub bound, the Roos bound and the shift bound from numerical experiments. In order to reduce computational time for the Schaub bound, we claim one conjecture, from numerical examples in binary and ternary cases with short code length that the Schaub bound can be set the value from only defining sequence of given code C.

This letter develops theoretical analysis of the normalized LMS algorithm (NLMSA) for use in complex-domain adaptive filters in the presence of impulse noise at filter input. We propose a new "stochastic" model for such impulse noise, and assume that filter reference input process is a white process, e.g., digital QAM data, White & Gaussian process, etc. In the analysis, we derive a simple difference equation for mean square tap weight misalignment (MSTWM). Experiment is carried out to demonstrate effectiveness of the NLMSA in robust filtering in the presence of the impulse noise at the filter input. Good agreement between simulated and theoretically calculated filter convergence, in a transient phase as well as in a steady-state, proves the validity of the analysis.

We present a novel, simple, efficient algorithm to generate random samples uniformly on the directional space of a cone. This algorithm has three advantages over the conventional non-uniform approach. First, to the best of our knowledge, this algorithm is original for uniformly sampling smaller areas of cones. Second, it is faster. Third, it always generates valid samples, which is not possible for the conventional approach.

Nonlinear modeling of complex irregular systems constitutes the essential part of many control and decision-making systems and fuzzy logic is one of the most effective algorithms to build such a nonlinear model. In this paper, a new approach to fuzzy modeling is proposed. The model considered herein is the well-known Sugeno-type fuzzy system. The fuzzy modeling algorithm suggested in this paper is composed of two phases: coarse tuning and fine tuning. In the first phase (coarse tuning), a successive clustering algorithm with the fuzzy validity measure (SCFVM) is proposed to find the number of the fuzzy rules and an initial fuzzy model. In the second phase (fine tuning), a moving genetic algorithm with partial encoding (MGAPE) is developed and used for optimized tuning of membership functions of the fuzzy model. Two computer simulation examples are provided to evaluate the performance of the proposed modeling approach and compare it with other modeling approaches.

It is known that any chordal graph can be uniquely decomposed into simplicial components. Based on this fact, it is shown that for a given chordal graph, its automorphism group can be computed in O((c!n)O(1)) time, where c denotes the maximum size of simplicial components and n denotes the number of nodes. It is also shown that isomorphism of those chordal graphs can be decided within the same time bound. From the viewpoint of polynomial-time computability, our result strictly strengthens the previous ones respecting the clique number.

We consider the problem of dynamically apportioning resources among a set of options in a worst-case online framework. The model we investigate is a generalization of the well studied online learning model. In particular, we allow the learner to see as additional information how high the risk of each option is. This assumption is natural in many applications like horse-race betting, where gamblers know odds for all options before placing bets. We apply Vovk's Aggregating Algorithm to this problem and give a tight performance bound. The results support our intuition that it is safe to bet more on low-risk options. Surprisingly, the loss bound of the algorithm does not depend on the values of relatively small risks.

Chen and Kanj considered the VERTEX COVER problem for graphs with perfect matchings (VC-PM). They showed that: (i) There is a reduction from general VERTEX COVER to VC-PM, which guarantees that if one can achieve an approximation factor of less than two for VC-PM, then one can do so for general VERTEX COVER as well. (ii) There is an algorithm for VC-PM whose approximation factor is given as 1.069+0.069 where is the average degree of the given graph. In this paper we improve (ii). Namely we give a new VC-PM algorithm which greatly outperforms the above one and its approximation factor is roughly . Our algorithm also works for graphs with "large" matchings, although its approximation factor is degenerated.

Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this problem in such a way that points are inserted one by one with uniformity preserved at every instance. Our criterion for uniformity is to minimize the gap ratio (which is the maximum gap over the minimum gap) at every point insertion. We present a linear time algorithm for finding an optimal n-point sequence with the maximum gap ratio bounded by in the 1-dimensional case. We describe how hard the same problem is for a point set in the plane and propose a local search heuristics for finding a good solution.

An instance of the classical stable marriage problem requires all participants to submit a strictly ordered preference list containing all members of the opposite sex. However, considering applications in real-world, we can think of two natural relaxations, namely, incomplete preference lists and ties in the lists. Either variation leaves the problem polynomially solvable, but it is known that finding a maximum cardinality stable matching is NP-hard when both variations are allowed. It is easy to see that the size of any two stable matchings differ by at most a factor of two, and so, an approximation algorithm with a factor two is trivial. A few approximation algorithms have been proposed with approximation ratio better than two, but they are only for restricted instances, such as restricting occurrence of ties and/or lengths of ties. Up to the present, there is no known approximation algorithm with ratio better than two for general inputs. In this paper, we give the first nontrivial result for approximation of factor less than two for general instances. Our algorithm achieves the ratio for an arbitrarily positive constant c, where N denotes the number of men in an input.

Over the years, many improvements and refinements to the backpropagation learning algorithm have been reported. In this paper, a new adaptive penalty-based learning extension for the backpropagation learning algorithm and its variants is proposed. The new method initially puts pressure on artificial neural networks in order to get all outputs for all training patterns into the correct half of the output range, instead of mainly focusing on minimizing the difference between the target and actual output values. The upper bound of the penalty values is also controlled. The technique is easy to implement and computationally inexpensive. In this study, the new approach is applied to the backpropagation learning algorithm as well as the RPROP learning algorithm. The superiority of the new proposed method is demonstrated though many simulations. By applying the extension, the percentage of successful runs can be greatly increased and the average number of epochs to convergence can be well reduced on various problem instances. The behavior of the penalty values during training is also analyzed and their active role within the learning process is confirmed.

Similar to algebraic decoding schemes, the (23, 12, 7) Golay code can be decoded by applying the step-by-step decoding algorithm. In this work, a modified step-by-step algorithm for decoding the Golay code is presented. Logical analysis yielded a simple rule for directly determining whether a bit in the received word is correct. The computational complexity can be reduced significantly using this scheme.

The minimum vertex ranking spanning tree problem is to find a spanning tree of G whose vertex ranking is minimum. This problem is NP-hard and no polynomial time algorithm for solving it is known for non-trivial classes of graphs other than the class of interval graphs. This paper proposes a polynomial time algorithm for solving the minimum vertex ranking spanning tree problem on outerplanar graphs.