We study the problem of transforming one list (vertex) coloring of a graph into another list coloring by changing only one vertex color assignment at a time, while at all times maintaining a list coloring, given a list of allowed colors for each vertex. This problem is known to be PSPACE-complete for bipartite planar graphs. In this paper, we first show that the problem remains PSPACE-complete even for bipartite series-parallel graphs, which form a proper subclass of bipartite planar graphs. We note that our reduction indeed shows the PSPACE-completeness for graphs with pathwidth two, and it can be extended for threshold graphs. In contrast, we give a polynomial-time algorithm to solve the problem for graphs with pathwidth one. Thus, this paper gives sharp analyses of the problem with respect to pathwidth.

A binary tree is regarded as a prefix-free binary code, in which the weighted sum of the lengths of root-leaf paths is equal to the expected codeword length. Huffman's algorithm computes an optimal tree in O(n log n) time, where n is the number of leaves. The problem was later generalized by allowing each leaf to have its own function of its depth and setting the sum of the function values as the objective function. The generalized problem was proved to be NP-hard. In this paper we study the case where every function is a unit step function, that is, a function that takes a lower constant value if the depth does not exceed a threshold, and a higher constant value otherwise. We show that for this case, the problem can be solved in O(n log n) time, by reducing it to the Coin Collector's problem.

The global avalanche characteristics measure the overall avalanche properties of Boolean functions, an n-variable balanced Boolean function of the sum-of-square indicator reaching σƒ=22n+2n+3 is an open problem. In this paper, we prove that there does not exist a balanced Boolean function with σƒ=22n+2n+3 for n≥4, if the hamming weight of one decomposition function belongs to the interval Q*. Some upper bounds on the order of propagation criterion of balanced Boolean functions with n (3≤n≤100) variables are given, if the number of vectors of propagation criterion is equal and less than 7·2n-3-1. Two lower bounds on the sum-of-square indicator for balanced Boolean functions with optimal autocorrelation distribution are obtained. Furthermore, the relationship between the sum-of-squares indicator and nonlinearity of balanced Boolean functions is deduced, the new nonlinearity improves the previously known nonlinearity.

In this paper, we propose an error-correction low-pass filter (EC-LPF) algorithm for estimating the wireless distance between devices. To measure this distance, the received signal strength indication (RSSI) is a popularly used method because the RSSI of a wireless signal, such as Wi-Fi and Bluetooth, can be measured easily without the need for additional hardware. However, estimating the wireless distance using an RSSI is known to be difficult owing to the occurrence of inaccuracies. To examine the inaccuracy characteristics of Bluetooth RSSI, we conduct a preliminary test to discover the relationship between the actual distance and Bluetooth RSSI under several different environments. The test results verify that the main reason for inaccuracy is the existence of measurement errors in the raw Bluetooth RSSI data. In this paper, the EC-LPF algorithm is proposed to reduce measurement errors by alleviating fluctuations in a Bluetooth signal with responsiveness for real-time applications. To evaluate the effectiveness of the EC-LPF algorithm, distance accuracies of different filtering algorithms are compared, namely, a low-pass filer (LPF), a Kalman filter, a particle filter, and the EC-LPF algorithm under two different environments: an electromagnetic compatibility (EMC) chamber and an indoor hall. The EC-LPF algorithm achieves the best performance in both environments in terms of the coefficient of determination, standard deviation, measurement range, and response time. In addition, we also implemented a meeting room application to verify the feasibility of the EC-LPF algorithm. The results prove that the EC-LPF algorithm distinguishes the inside and outside areas of a meeting room without error.

This paper proposes a novel blind adaptive array scheme with subcarrier transmission power assignment (STPA) for spectrum superposing in cognitive radio networks. The Eigenvector Beamspace Adaptive Array (EBAA) is known to be one of the blind adaptive array algorithms that can suppress inter-system interference without any channel state information (CSI). However, EBAA has difficulty in suppressing interference signals whose Signal to Interference power Ratio (SIR) values at the receiver are around 0dB. With the proposed scheme, the ST intentionally provides a level difference between subcarriers. At the receiver side, the 1st eigenvector of EBAA is applied to the received signals of the subcarrier assigned higher power and the 2nd eigenvector is applied to those assigned lower power. In order to improve interference suppression performance, we incorporate Beamspace Constant Modulus Algorithm (BSCMA) into EBAA (E-BSCMA). Additionally, STPA is effective in reducing the interference experienced by the primary system. Computer simulation results show that the proposed scheme can suppress interference signals received with SIR values of around 0dB while improving operational SIR for the primary system. It can enhance the co-existing region of 2 systems that share a spectrum.

Optimizing embedded software is a problem having scientific and practical signification. Optimizing embedded software can be done in different phases of the software life cycle under different optimal conditions. Most studies of embedded software optimization are done in forward engineering and these studies have not given an overall model for the optimization problem of embedded software in both forward engineering and reverse engineering. Therefore, in this paper, we propose a new approach to embedded software optimization based on reverse engineering. First, we construct an overall model for the embedded software optimization in both forward engineering and reverse engineering and present a process of embedded software optimization in reverse engineering. The main idea of this approach is that decompiling executable code to source code, converting the source code to models and optimizing embedded software under different levels such as source code and model. Then, the optimal source code is recompiled. To develop this approach, we present two optimization techniques such as optimizing power consumption of assembly programs based on instruction schedule and optimizing performance based on alternating equivalent expressions.

This paper proposes a novel greedy algorithm, called Creditability-Estimation based Matching Pursuit (CEMP), for the compressed sensing signal recovery. As proved in the algorithm of Stagewise Orthogonal Matching Pursuit (StOMP), two Gaussian distributions are followed by the matched filter coefficients corresponding to and without corresponding to the actual support set of the original sparse signal, respectively. Therefore, the selection for each support point is interpreted as a process of hypothesis testing, and the preliminarily selected support set is supposed to consist of rejected atoms. A hard threshold, which is controlled by an input parameter, is used to implement the rejection. Because the Type I error may happen during the hypothesis testing, not all the rejected atoms are creditable to be the true support points. The creditability of each preliminarily selected support point is evaluated by a well-designed built-in mechanism, and the several most creditable ones are adaptively selected into the final support set without being controlled by any extra external parameters. Moreover, the proposed CEMP does not necessitate the sparsity level to be a priori control parameter in operation. In order to verify the performance of the proposed algorithm, Gaussian and Pulse Amplitude Modulation sparse signals are measured in the noiseless and noisy cases, and the experiments of the compressed sensing signal recoveries by several greedy algorithms including CEMP are implemented. The simulation results show the proposed CEMP can achieve the best performances of the recovery accuracy and robustness as a whole. Besides, the experiment of the compressed sensing image recovery shows that CEMP can recover the image with the highest Peak Signal to Noise Ratio (PSNR) and the best visual quality.

We propose a novel bias-free adaptive beamformer employing an affine projection algorithm with the optimal regularization parameter. The generalized sidelobe canceller affine projection algorithm suffers from a bias of a weight vectors under the condition of no reference signals for output of an array in the beamforming application. First, we analyze the bias in the algorithm and prove that the bias can be eliminated through a large regularization parameter. However, this causes slow convergence at the initial state, so the regularization parameter should be controlled. Through the optimization of the regularization parameter, the proposed method achieves fast convergence without the bias at the steady-state. Experimental results show that the proposed beamformer not only removes the bias but also achieves both fast convergence and high steady-state output signal-to-interference-plus-noise ratio.

A feedback vertex set F of an undirected graph G is a vertex subset of G whose removal results in a forest. Such a set F is said to be independent if F forms an independent set of G. In this paper, we study the problem of finding an independent feedback vertex set of a given graph with the minimum number of vertices, from the viewpoint of graph classes. This problem is NP-hard even for planar bipartite graphs of maximum degree four. However, we show that the problem is solvable in linear time for graphs having tree-like structures, more specifically, for bounded treewidth graphs, chordal graphs and cographs. We then give a fixed-parameter algorithm for planar graphs when parameterized by the solution size. Such a fixed-parameter algorithm is already known for general graphs, but our algorithm is exponentially faster than the known one.

To ensure the security of image transmission, this paper presents a new image encryption algorithm based on a genetic algorithm (GA) and a piecewise linear chaotic map (PWLCM), which adopts the classical diffusion-substitution architecture. The GA is used to identify and output the optimal encrypted image that has the highest entropy value, the lowest correlation coefficient among adjacent pixels and the strongest ability to resist differential attack. The PWLCM is used to scramble pixel positions and change pixel values. Experiments and analyses show that the new algorithm possesses a large key space and resists brute-force, statistical and differential attacks. Meanwhile, the comparative analysis also indicates the superiority of our proposed algorithm over a similar, recently published, algorithm.

A renal biopsy is a procedure to get a small piece of kidney for microscopic examination. With the development of tissue sectioning and medical imaging techniques, microscope renal biopsy image sequences are consequently obtained for computer-aided diagnosis. This paper proposes a new context-based segmentation algorithm for acquired image sequence, in which an improved genetic algorithm (GA) patching method is developed to segment different size target. To guarantee the correctness of first image segmentation and facilitate the use of context information, a boundary fusion operation and a simplified scale-invariant feature transform (SIFT)-based registration are presented respectively. The experimental results show the proposed segmentation algorithm is effective and accurate for renal biopsy image sequence.

In this paper, we introduce a promising iterative interference alignment (IA) strategy for multiple-input multiple-output (MIMO) multi-cell downlink networks, which utilizes the channel reciprocity between uplink/downlink channels. We intelligently combine iterative beamforming and downlink IA issues to design an iterative multiuser MIMO IA algorithm. The proposed scheme uses two cascaded beamforming matrices to construct a precoder at each base station (BS), which not only efficiently reduce the effect of inter-cell interference from other-cell BSs, referred to as leakage of interference, but also perfectly eliminate intra-cell interference among spatial streams in the same cell. The transmit and receive beamforming matrices are iteratively updated until convergence. Numerical results indicate that our IA scheme exhibits higher sum-rates than those of the conventional iterative IA schemes. Note that our iterative IA scheme operates with local channel state information, no time/frequency expansion, and even relatively a small number of mobile stations (MSs), unlike opportunistic IA which requires a great number of MSs.

An on-channel repeater (OCR) performing simultaneous reception and transmission at the same frequency is beneficial to improve spectral efficiency and coverage. In an OCR, it is important to cancel the feedback interference caused by imperfect isolation between the transmit and receive antennas, and least mean square (LMS) based adaptive filters are commonly used for this purpose. In this paper, we analyze the performance of the LMS based adaptive feedback canceller in terms of its transient behavior and the steady-state mean square error (MSE). Through a theoretical analysis, we derive iterative equations to compute transient MSEs and provide a procedure to simply evaluate steady-state MSEs for the adaptive feedback canceller. Simulation results performed to verify the theoretical MSEs show good agreement between the proposed theoretical analysis and the empirical results.

A constant multiplier performs a multiplication of a data-input with a constant value. Constant multipliers are essential components in various types of arithmetic circuits, such as filters in digital signal processor (DSP) units, and they are prevalent in modern VLSI designs. This study presents an efficient algorithm and fast hardware implementation for performing multiply-by-(1+2k) operation with additions. No multiplications are needed. The value of (1+2k)N can be computed by adding N to its k-bit left-shifted value 2kN. The additions can be performed by the full-adder-based (FA-based) ripple carry adder (RCA) for simple architecture. This paper introduces the unit cells for additions (UCAs) to construct the UCA-based RCA which achieves 35% faster than the FA-based RCA in speed performance. Further, in order to improve the speed performance, a simple and modular hybrid adder is presented with the proposed UCA concept, where the carry lookahead adder (CLA) as a module and many of the CLA modules are serially connected in a fashion similar to the RCA. Results show that the hybrid adder significantly improves the speed performance.

This paper presents a downlink interference mitigation framework for two-tier heterogeneous networks, that consist of spectrum-sharing macrocells and femtocells*. This framework establishes cooperation between the two tiers through two algorithms, namely, the restricted waterfilling (RWF) algorithm and iterative reweighted least squares interference alignment (IRLS-IA) algorithm. The proposed framework models the macrocell-femtocell two-tier cellular system as an overlay cognitive radio system in which the macrocell system plays the role of the primary user (PU) while the femtocell networks play the role of the cognitive secondary users (SUs). Through the RWF algorithm, the macrocell basestation (MBS) cooperates with the femtocell basestations (FBSs) by releasing some of its eigenmodes to the FBSs to do their transmissions even if the traffic is heavy and the MBS's signal to noise power ratio (SNR) is high. Then, the FBSs are expected to achieve a near optimum sum rate through employing the IRLS-IA algorithm to mitigate both the co-tier and cross-tier interference at the femtocell users' (FUs) receivers. Simulation results show that the proposed IRLS-IA approach provides an improved sum rate for the femtocell users compared to the conventional IA techniques, such as the leakage minimization approach and the nuclear norm based rank constraint rank minimization approach. Additionally, the proposed framework involving both IRLS-IA and RWF algorithms provides an improved total system sum rate compared with the legacy approaches for the case of multiple femtocell networks.

This paper considers the problem of enumerating all maximal cliques in unit disk graphs, which is a plausible setting for applications of finding similar data groups. Our primary interest is to develop a faster algorithm using the geometric structure about the metric space where the input unit disk graph is embedded. Assuming that the distance between any two vertices is available, we propose a new algorithm based on two well-known algorithms called Bron-Kerbosch and Tomita-Tanaka-Takahashi. The key idea of our algorithm is to find a good pivot quickly using geometric proximity. We validate the practical impact of our algorithm via experimental evaluations.

Users of wireless mobile devices need Internet access not only when they stay at home or office, but also when they travel. It may be desirable for such users to select a "longcut route" from their current location to his/her destination that has longer travel time than the shortest route, but provides a better mobile wireless environment. In this paper, we formulate the above situation as the optimization problem of “optimal longcut route selection”, which requires us to find the best route concerning the wireless environment subject to a travel time constraint. For this new problem, we show NP-hardness, propose two pseudo-polynomial time algorithms, and experimental evaluation of the algorithms.

Computing an invariant of a graph such as treewidth and pathwidth is one of the fundamental problems in graph algorithms. In general, determining the pathwidth of a graph is NP-hard. In this paper, we propose several reduction methods for decreasing the instance size without changing the pathwidth, and implemented the methods together with an exact algorithm for computing pathwidth of graphs. Our experimental results show that the number of vertices in all chemical graphs in NCI database decreases by our reduction methods by 53.81% in average.

In automotive frequency modulated continuous wave (FMCW) radar based on multiple ramps with different slope, an effective pairing algorithm is required to simultaneously detect the target range and velocity. That is, as finding beat-frequencies intersecting at a single point of the range-Doppler map, we extract the range and velocity of a target. Unlike the ideal case, however, in a real radar system, even though multiple beat frequencies are originated from the same target, these beat frequencies have many different intersection values, resulting in mismatch pairing during the pairing step. Moreover, this problem also reduces the detection accuracy and the radar detection performance. In this study, we found that mismatch pairing is caused by the round-off errors of the range-beat frequency and Doppler frequency, as well as their various combinations in the discrete frequency domain. We also investigated the effect of mismatch pairing on detection performance, and proposed a new approach to minimize this problem. First, we propose integer and half-integer frequency position-based pairing method during extraction of the range and Doppler frequencies in each ramp to increase detection accuracy. Second, we propose a window-based pairing method to identify the same target from range-Doppler frequencies extracted in the first step. We also find the appropriate window size to overcome pairing mismatch. Finally, we propose the method to obtain a higher accuracy of range and velocity by weighting the values determined in one window. To verify the detection performance of the proposed method by comparison with the typical method, simulations were conducted. Then, in a real field test using the developed radar prototype, the detection probability of the proposed algorithm showed more than 60% improvement in comparison with the conventional method.

Least squares error (LSE) method adopted recursively can be used to track the frequency and amplitude of signals in steady states and kinds of non-steady ones in power system. Taylor expansion is used to give another version of this recursive LSE method. Aided by variable-windowed short-time discrete Fourier transform, recursive LSEs with and without Taylor expansion converge faster than the original ones in the circumstance of off-nominal input singles. Different versions of recursive LSE were analyzed under various states, such as signals of off-nominal frequency with harmonics, signals with step changes, signals modulated by a sine signal, signals with decaying DC offset and additive Gaussian white noise. Sampling rate and data window size are two main factors influencing the performance of method recursive LSE in transient states. Recursive LSE is sensitive to step changes of signals, but it is in-sensitive to signals' modulation and singles with decaying DC offset and noise.