The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.

Given a simple graph G with n vertices, m edges and k connected components. The spanning forest problem is to find a spanning tree for each connected component of G. This problem has applications to the electrical power demand problem, computer network design, circuit analysis, etc. An optimal parallel algorithm for finding a spanning tree on the trapezoid graph is given by Bera et al., it takes O(log n) time with O(n/log n) processors on the EREW (Exclusive-Read Exclusive-Write) PRAM. Bera et al.'s algorithm is very simple and elegant. Moreover, it can correctly construct a spanning tree when the graph is connected. However, their algorithm can not accept a disconnected graph as an input. Applying their algorithm to a disconnected graph, Concurrent-Write occurs once for each connected component, thus this can not be achieved on EREW PRAM. In this paper we present an O(log n) time parallel algorithm with O(n/log n) processors for constructing a spanning forest on trapezoid graph G on EREW PRAM even if G is a disconnected graph.

In this paper, we propose δ-similar elimination to improve the search performance of multiobjective evolutionary algorithms in combinatorial optimization problems. This method eliminates similar individuals in objective space to fairly distribute selection among the different regions of the instantaneous Pareto front. We investigate four eliminating methods analyzing their effects using NSGA-II. In addition, we compare the search performance of NSGA-II enhanced by our method and NSGA-II enhanced by controlled elitism.

A branch-and-bound algorithm (BB for short) is the most general technique to deal with various combinatorial optimization problems. Even if it is used, computation time is likely to increase exponentially. So we consider its parallelization to reduce it. It has been reported that the computation time of a parallel BB heavily depends upon node-variable selection strategies. And, in case of a parallel BB, it is also necessary to prevent increase in communication time. So, it is important to pay attention to how many and what kind of nodes are to be transferred (called sending-node selection strategy). In this paper, for the graph coloring problem, we propose some sending-node selection strategies for a parallel BB algorithm by adopting MPI for parallelization and experimentally evaluate how these strategies affect computation time of a parallel BB on a PC cluster network.

We present a TCP flow level performance evaluation on error rate aware scheduling algorithms in Evolved UTRA and UTRAN networks. With the introduction of the error rate, which is the probability of transmission failure under a given wireless condition and the instantaneous transmission rate, the transmission efficiency can be improved without sacrificing the balance between system performance and user fairness. The performance comparison with and without error rate awareness is carried out dependant on various TCP traffic models, user channel conditions, schedulers with different fairness constraints, and automatic repeat request (ARQ) types. The results indicate that error rate awareness can make the resource allocation more reasonable and effectively improve the system and individual performance, especially for poor channel condition users.

We propose a fast decoding algorithm for the p-ary first-order Reed-Muller code guaranteeing correction of up to errors and having complexity proportional to nlog n, where n = pm is the code length and p is an odd prime. This algorithm is an extension in the complex domain of the fast Hadamard transform decoding algorithm applicable to the binary case.

Let G =(V, E) be an undirected simple graph with u ∈ V. If there exist any two vertices in G whose distance becomes longer when a vertex u is removed, then u is defined as a hinge vertex. Finding the set of hinge vertices in a graph is useful for identifying critical nodes in an actual network. A number of studies concerning hinge vertices have been made in recent years. In a number of graph problems, it is known that more efficient sequential or parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs in O(log n) time with O(n/log n) processors on EREW PRAM for finding all hinge vertices of a circular-arc graph.

In this paper, an evolutionary approach is proposed to obtain a discrete-time state-space interval model for uncertain continuous-time systems having interval uncertainties. Based on a worst-case analysis, the problem to derive the discrete interval model is first formulated as multiple mono-objective optimization problems for matrix-value functions associated with the discrete system matrices, and subsequently optimized via a proposed genetic algorithm (GA) to obtain the lower and upper bounds of the entries in the system matrices. To show the effectiveness of the proposed approach, roots clustering of the characteristic equation of the obtained discrete interval model is illustrated for comparison with those obtained via existing methods.

Software rejuvenation is a preventive and proactive solution that is particularly useful for counteracting the phenomenon of software aging. In this article, we consider periodic software rejuvenation models based on the expected cost per unit time in the steady state under discrete-time operation circumstance. By applying the discrete renewal reward processes, we describe the stochastic behavior of a telecommunication billing application with a degradation mode, and determine the optimal periodic software rejuvenation schedule minimizing the expected cost. Similar to the earlier work by the same authors, we develop a statistically non-parametric algorithm to estimate the optimal software rejuvenation schedule, by applying the discrete total time on test concept. Numerical examples are presented to estimate the optimal software rejuvenation schedules from the simulation data. We discuss the asymptotic behavior of estimators developed in this paper.

A new structure learning approach for Bayesian networks (BNs) based on dual genetic algorithm (DGA) is proposed in this paper. An individual of the population is represented as a dual chromosome composed of two chromosomes. The first chromosome represents the ordering among the BN nodes and the second represents the conditional dependencies among the ordered BN nodes. It is rigorously shown that there is no BN structure that cannot be encoded by the proposed dual genetic encoding and the proposed encoding explores the entire solution space of the BN structures. In contrast with existing GA-based structure learning methods, the proposed method learns not only the topology of the BN nodes, but also the ordering among the BN nodes, thereby, exploring the wider solution space of a given problem than the existing method. The dual genetic operators are closed in the set of the admissible individuals. The proposed method is applied to real-world and benchmark applications, while its effectiveness is demonstrated through computer simulation.

Because of its simplicity and intuitive approach, point-based rendering has been a very popular research area. Recent approaches have focused on hardware-accelerated techniques. By applying a deferred shading scheme, both high-quality images and high-performance rendering have been achieved. However, previous methods showed problems related to depth-based visibility computation. We propose an extended point-based rendering method using a visibility map. In our method we employ a distance-based visibility technique (replacing depth-based visibility), an averaged position map and an adaptive fragment processing scheme, resulting in more accurate and improved image quality, as well as improved rendering performance.

The recent progress in sensor and wireless communication technologies has enabled the design and implementation of new applications such as sensor telemetry which is the use of wireless sensors to gather fine-grained information from products, people and places. In this work, we consider a realistic telemetry application in which an area is periodically monitored by a sensor network which gathers data from equally spaced sample points. The objective is to maximize the lifetime of the network by jointly selecting the sensing nodes, the node transmission powers and the route to the base station from each sensing node. We develop an optimization-based algorithm OPT-RE and a low complexity algorithm SP-RE for this purpose and analyze their dynamics through extensive numerical studies. Our results indicate that SP-RE is a promising algorithm which has comparable performance to that of the more computationally intensive OPT-RE algorithm. The energy consumption is significantly affected by the channel access method, and in this paper, we also compare the effects of the collision free TDMA and contention based CSMA/CA methods. We propose practical enhancements to CSMA/CA so that the energy consumption due to collisions is reduced. Our simulation results indicate that with the proposed enhancements contention based channel access can provide comparable performance to that of the collision free methods.

In this paper we introduce an area and power efficient fully-parallel LDPC decoder design, which keeps the BER performance while consuming less hardware resources and lower power compared with conventional decoders. For this decoder, we firstly propose two improved simplified min-sum algorithms, which enable the decoder to reduce the hardware implementation complexity and area: hardware consumption of check operation module is reduced by 40%, while achieving a negligible performance loss compared with the general min-sum algorithm. To reduce the power dissipation of the decoder, we also proposed a power-saved strategy, according to which the message evolution halts as the parity-check condition is satisfied. This strategy reduces more than 50% power under good channel condition. The synthesis result in 0.18 µm CMOS technology shows our decoder based on (648,540) irregular LDPC code of WLAN (802.11n) protocol achieves 810 [Mbps] throughput with 283 [mW] power consumption.

This paper proposes a new type of compact waveguide directional coupler, which is constructed from two crossed E-plane rectangular waveguide with two metallic posts in the square junction and one metallic post at each port. The metallic posts in the square junction are set symmetrically along a diagonal line to obtain the directivity properties. The metallic post inserted at each input/output waveguide port can realize a matched state. Tight-coupling properties 0.79-6 dB are realized by optimizing the dimension of the junction and the positions/radii of the posts. The design results are verified by an em-simulator (Ansoft HFSS) and experiments.

The size-dependent array problem is a problem with systolic arrays such that the size of systolic arrays limits the size of calculations, which in a do-loop structure controls how many times it is repeated and how deep the nesting loops are. A systolic array cannot deal with larger calculations. For the size-dependent array problem, a spiral systolic array has been studied so far. It has non-adjacent connections between PEs, such as loop paths for sending data back so that data flows over the array independently of its own size. This paper takes an approach to the problem without non-adjacent connections. This paper discusses systolic messy arrays for infinite iterative algorithms so that they are independent from the size of calculations. First a systolic messy array called two-square shape is introduced then the properties of two-square shape are summarized: memory function, cyclic addition, and cyclic multiplication. Finally a way of building systolic messy arrays that calculate infinite iterative algorithms is illustrated with concrete examples such as an arithmetic progression, a geometric progression, N factorial, and Fibonacci numbers.

In recent years, network analysis has revealed that some real networks have the properties of small-world and/or scale-free networks. In this study, a simple Genetic Algorithm (GA) is regarded as a network where each node and each edge respectively represent a population and the possibility of the transition between two nodes. The characteristic path length (CPL), which is one of the most popular criteria in small-world networks, is derived analytically and shows how much the crossover operation affects the path length between two populations. As a result, the crossover operation is not so useful for shortening the CPL.

It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.

An edge-weighted directed graph is referred to as a network in this paper, and an edge operation is an operation that increases or decreases an edge weight. Decreasing an edge weight from the infinite to a finite value or increasing any edge weight from a finite one to the infinite corresponds to addition or deletion of this edge, respectively. The dynamic shortest path problem (DSPP for short) is defined by "Given any network with a specified vertex (denoted as s), and any sequence of edge operations, construct a shortest path tree of each network obtained by executing those edge operations one by one in the order of the sequence." As an application, fast routing for an interior network using link state protocols, such as OSPF and IS-IS, requires solving DSPP efficiently. In this paper, among as many existing algorithms as possible, including those which execute several edge operations simultaneously, fundamental and/or important algorithms are implemented and their capability is evaluated based on the results of computational experiments.

Localization of mobile terminals has received considerable attention in wireless communications. In this letter, we present a covariance shaping least squares (CSLS) estimator using time-of-arrival measurements of the signal from the mobile station received at three or more base stations. It is shown that the CSLS estimator yields better performance than the other LS estimators at low signal-to-noise ratio conditions.

Low-density parity-check (LDPC) codes are one of the most powerful error correcting codes and are attracting much attention these days. LDPC codes are promising for communications and broadcasting as well where the use of error correcting codes are essential. LDPC codes have been standardized in some communication standards, such as, IEEE802.16e, DVB-S2, IEEE802.3an (10BASE-T), and so on. The performance of LDPC codes largely depend on their code structure and decoding algorithm. In this paper, we present the basics of LDPC codes and their decoding algorithms. We also present some LDPC codes that have good performance and are receiving much attention particularly in communication systems. We also overview some standardized LDPC codes, the LDPC codes standardized in DVB-S2 and the IEEE802.16e standard LDPC codes. Moreover, we present some research on LDPC coded MIMO systems and HARQ using LDPC codes.