We study the problem of finding the smallest power of an input graph that has <em>k</em> disjoint dominating sets, where the <em>i</em>th power of an input graph <em>G</em> is constructed by adding edges between pairs of vertices in <em>G</em> at distance <em>i</em> or less, and a subset of vertices in a graph <em>G</em> is a dominating set if and only if every vertex in <em>G</em> is adjacent to a vertex in this subset.   The problem is a different view of the <em>d</em>-domatic number problem in which the goal is to find the maximum number of disjoint dominating sets in the <em>d</em>th power of the input graph.   This problem is motivated by applications in multi-facility location and distributed networks. In the facility location framework, for instance, there are <em>k</em> types of services that all clients in different regions of a city should receive. A graph representing the map of regions in the city is given where the nodes of the graph represent regions and neighboring regions are connected by edges. The problem is how to establish facility servers in the city (each region can host at most one server) such that every client in the city can access a facility server in its region or in a region in the neighborhood. Since it may not be possible to find a facility location satisfying this condition, "a region in the neighborhood" required in the question is modified to "a region at the minimum possible distance <em>d</em>".   In this thesis, we study the connection of the above-mentioned problem with similar problems including the domatic number problem and the <em>d</em>-domatic number problem. We show that the problem is NP-complete for any fixed <em>k</em> greater than two even when the input graph is restricted to split graphs, <em>2</em>-connected graphs, or planar bipartite graphs of degree four. In addition, the problem is in P for bounded tree-width graphs, when considering <em>k</em> as a constant, and for strongly chordal graphs, for any <em>k</em>. Then, we provide a slightly simpler proof for a known upper bound for the problem. We also develop an exact (exponential) algorithm for the problem, running in time <em>O</em>(2. 73^<em>n</em>). Moreover, we prove that the problem cannot be approximated within ratio smaller than <em>2</em> even for split graphs, <em>2</em>-connected graphs, and planar bipartite graphs of degree four. We propose a greedy <em>3</em>-approximation algorithm for the problem in the general case, and other approximation ratios for permutation graphs, distance-hereditary graphs, cocomparability graphs, dually chordal graphs, and chordal graphs. Finally, we list some directions for future work.

Piercing problems arise often in facility location, which is a well-studied area of computational geometry. The general form of the piercing problem discussed in this dissertation asks for the minimum number of facilities for a set of given rectangular demand regions such that each region has at least one facility located within it. It has been shown that even if all regions are uniform sized squares, the problem is NP-hard. Therefore we concentrate on approximation algorithms for the problem. As the known approximation ratio for arbitrarily sized rectangles is poor, we restrict our effort to designing approximation algorithms for unit-height rectangles. Our e-approximation scheme requires <I>n</I>^{<I>O</I>(1/&epsilon;²)} time. We also consider the problem with restrictions like bounding the depth of a point and the width of the rectangles. The approximation schemes for these two cases take <I>n</I>^{<I>O</I>(1/&epsilon;)} time. We also show how to maintain a factor 2 approximation of the piercing set in <I>O</I>(log <I>n</I>) amortized time in an insertion-only scenario.

We study the problem of finding the smallest power of an input graph that has <em>k</em> disjoint dominating sets, where the <em>i</em>th power of an input graph <em>G</em> is constructed by adding edges between pairs of vertices in <em>G</em> at distance <em>i</em> or less, and a subset of vertices in a graph <em>G</em> is a dominating set if and only if every vertex in <em>G</em> is adjacent to a vertex in this subset.   The problem is a different view of the <em>d</em>-domatic number problem in which the goal is to find the maximum number of disjoint dominating sets in the <em>d</em>th power of the input graph.   This problem is motivated by applications in multi-facility location and distributed networks. In the facility location framework, for instance, there are <em>k</em> types of services that all clients in different regions of a city should receive. A graph representing the map of regions in the city is given where the nodes of the graph represent regions and neighboring regions are connected by edges. The problem is how to establish facility servers in the city (each region can host at most one server) such that every client in the city can access a facility server in its region or in a region in the neighborhood. Since it may not be possible to find a facility location satisfying this condition, "a region in the neighborhood" required in the question is modified to "a region at the minimum possible distance <em>d</em>".   In this thesis, we study the connection of the above-mentioned problem with similar problems including the domatic number problem and the <em>d</em>-domatic number problem. We show that the problem is NP-complete for any fixed <em>k</em> greater than two even when the input graph is restricted to split graphs, <em>2</em>-connected graphs, or planar bipartite graphs of degree four. In addition, the problem is in P for bounded tree-width graphs, when considering <em>k</em> as a constant, and for strongly chordal graphs, for any <em>k</em>. Then, we provide a slightly simpler proof for a known upper bound for the problem. We also develop an exact (exponential) algorithm for the problem, running in time <em>O</em>(2. 73^<em>n</em>). Moreover, we prove that the problem cannot be approximated within ratio smaller than <em>2</em> even for split graphs, <em>2</em>-connected graphs, and planar bipartite graphs of degree four. We propose a greedy <em>3</em>-approximation algorithm for the problem in the general case, and other approximation ratios for permutation graphs, distance-hereditary graphs, cocomparability graphs, dually chordal graphs, and chordal graphs. Finally, we list some directions for future work.

In passive RFID systems, how to reduce the collision among tags is an important issue at the medium access control layer. The Framed Slotted ALOHA and its variations are well-known anti-collision algorithms for RFID systems. However, when the Framed Slotted ALOHA is used, the system efficiency and the average time delay deteriorate rapidly when the total number of tags increases. On the other hand, the total number of slots in a frame can¡¦t be infinity. In this thesis, we first compare existing anti-collision protocols and then propose a novel algorithm based on the Enhanced Dynamic Framed Slotted ALOHA (EDFSA) and the Progressing Scanning (PS) algorithm. The proposed algorithm is called Dynamic Grouping (DG). The DG algorithm partitions the RFID tags according to the distances from tags to the reader in order to avoid using too many slots in a frame. Inparticular, the DG algorithm estimates the spatial distribution of tags based on previous scanning results and then adjusts the partition accordingly. Unlike PS algorithm, the DG algorithm is applicable when the RFID tags are uniformly distributed or normally distributed.

Feature selection is a pre-processing step in data-mining and machine learning, and plays an important role for analyzing high-dimensional data. Appropriately selected features can not only reduce the complexity of the mining or learning process, but also improve the accuracy of results. In the past, the concept of performing the task of feature selection by attribute clustering was proposed. If similar attributes could be clustered into groups, attributes could be easily replaced by others in the same group when some attribute values were missed. Hong et al. also proposed several genetic algorithms for finding appropriate attribute clusters. Their approaches, however, suffered from the weakness that multiple chromosomes would represent the same attribute clustering result (feasible solution) due to the combinatorial property, thus causing a larger search space than needed. In this thesis, we thus attempt to improve the performance of the GA-based attribute-clustering process based on the grouping genetic algorithm (GGA). Two GGA-based attribute clustering approaches are proposed. In the first approach, the general GGA representation and operators are used to reduce the redundancy of chromosome representation for attribute clustering. In the second approach, a new encoding scheme with corresponding crossover and mutation operators are designed, and an improved fitness function is proposed to achieve better convergence speed and provide more flexible alternatives than the first one. At last, experiments are made to compare the efficiency and the accuracy of the proposed approaches and the previous ones.

Nowadays, Internet plays an indispensable role in human lives. People use Internet to search information, transmit data, download ?le, and so on. The data transformed to the composed digital signal by ¡¦0¡¦ and ¡¦1¡¦ are transmitted on Internet . However, Internet is open and unreliable, data may be stolen from the other people if they are not encrypted. In order to ensure the security and secret of data, the cryptosystem is very important. RSA is a famous public-key cryptosystem, and it has easy concept and high security. It needs a lot of modular exponentiations while encryption or decryption. The key length of RSA is always larger than 1024 bits to ensure the high security. In order to achieve real time transmission, we have to speed up the RSA cryptosystem. Therefore, it must be implemented on hardware. In RSA cryptosystem, modular exponentiation is the only operation. Modular exponentiation is based on modular multiplications. Montgomery¡¦s Algorithm used simple additions and shifts to implement the complex modular multiplication. Because the key length is usually larger than 1024 bits, some signals have a lot of fan-outs in hardware architecture. Therefore, the signals have to connect buffers to achieve enough driving ability. But, it may lead to longer delay time and more power consumption. So, Tenca et al. proposed a Multiple Word Montgomery Algorithm to improve the problem of fan-out. Recently, Huang et al. proposed an algorithm which can reduce data dependency of Tenca¡¦s algorithm. This research is based on the architecture of Huang¡¦s algorithm and detects the redundant operations. Then, we block the unnecessary signals to reduce the switch activities. Besides, we use low power shift register to reduce the power consumption of shift register. Experimental results show that our design is useful on decreasing power consumption.

In this paper we propose two simple algorithms to estimate parameters £] and baseline survival function in Cox proportional hazard model with application to Massachusetts Health Care Panel Study (MHCPS) (Chappell, 1991) data which is a left truncated and interval censored data. We find that, in the estimation of £] and baseline survival function, Kaplan and Meier algorithm is uniformly better than the Empirical algorithm. Also, Kaplan and Meier algorithm is uniformly more powerful than the Empirical algorithm in testing whether two groups of survival functions are the same. We also define a distance measure D and compare the performance of these two algorithms through £] and D.

To determine the maximum rectangular block (MRB) from a rare material as larger as possible indicates to increase of the rate of material usage. The cutting problem has been addressed since 1984. But its applications were strongly restricted due to simple definition of the cutting problem. In order to expand the area of applications, in this dissertation, a general cutting problem will be considered. At first, the rectangular boundary of the original material is replaced by an arbitrary closed region. Due to the general material profile, many other materials can be involved. When the maximum rectangular block has been obtained, the remaining closed space (RCS) of the material can be divided again. A blind search algorithm (BSA), which globally searches the MRB point-by-point from the boundary points of the contour, will be developed. The BSA is able to acquire the MRB from mother material continuously from larger areas to smaller ones until a predefined threshold value is reached. Although the MRB in an arbitrary closed region can be successfully resolved, two problems are still unsolved. The first limitation is that both edges of the MRB must be parallel with image axes. The second limitation is that the mother material needs to be uniform, i.e., no defects inside the material. In order to release these two assumptions, some algorithms will be presented. Applications of those techniques to the leather material will be demonstrated. In spite of resolving the cutting problem by the presented algorithms, a possible improvement is needed for larger MRBs. The challenge about larger MRBs is that how to make the searching process more efficiently. Therefore, two new methods of GA to obtain the MRB are proposed. By comparing the results using the BSA, the GA approaches are verified to be able to reach the near-optimal performance. Even though only leather material is focused in this research, the proposed methods can be easily extended to other industrial materials, especially for those expensive materials.

The growing extent and variety of present military operations forces to use the resources in hand at its best. Especially, the optimum usage and assignment of limited number of the air force resources to missions will provide a considerable advantage in the battle field. The problem of finding the feasible and optimum assignment has been known to be studied / yet performing the process faster is still a topic that captures researchers&rsquo / attention because of the computational complexity that the assignment problem involves within. In this thesis, exploring the optimal assignment of fleets/aircrafts to targets/groups of targets is going to be performed via algorithms and heuristics. As the best choice for finding the exact solution, Branch-and-Bound algorithm, which is an intelligent way of searching for the solution on a solution tree where the nodes with potential of not leading to the solution are fathomed, has been investigated and applied according to the specific problem needs. The number of nodes on the search tree increases exponentially as the problem size increases. Moreover / as the size of the assignment problem increases, attaining the solution solely by Branch-and-Bound algorithm is definitely computationally expensive due to memory and time requirements. Therefore, Genetic algorithm which can provide good solutions in a relatively short time without having computational difficulties is considered as the second algorithm. Branch-and-Bound algorithm and Genetic algorithm are separately used for obtaining the solution. Hybrid algorithms which are combinations of Branch-and-Bound and Genetic algorithms are used with heuristics for improving the results.

In this thesis, the multi-carrier (MC) code division multiple access (CDMA) system is considered in Rayleigh fading channel. The main concern of this thesis is to devise a new direct linearly constrained constant modulus (LCCM) inverse QRD-RLS algorithm for multiple access interference (MAI) cancellation and the problem due to the mismatch of the channel estimator. In the conventional approach, two significant detectors are applied to the system for multiuser interference suppression, one is the blind adaptation algorithm and the other is adaptive linearly constrained PLIC approach. However, the mirror effect may occur when the blind adaptation algorithm is employed. It might affect the performance in terms of bit error rate (BER), although the desired signal to interference (due to other users) improvement is still acceptable. Moreover, in case that the channel coefficients could not be estimated perfectly, the mismatch problem may occur to degrade the performance of the adaptive linearly constrained PLIC approach with the LMS or RLS algorithm. To overcome the mismatch problem, the conventional approach is to use the LCCM criterion with gradient algorithm. However, the convergence rate of the gradient algorithm is too slow to be implemented in real-time wireless communication system. In this thesis, to have fast convergence rate and to circumvent the mismatch problem, the robust LCCM-IQRD algorithm is devised and applied to the MC-CDMA system in Rayleigh fading channel. The proposed robust LCCM-IQRD algorithm has shown to be more effective in terms of MAI cancellation and the mismatch due to imperfect channel estimator. The performance, in terms of BER, of the proposed algorithm is superior to that of the conventional PLIC based algorithms, the blind adaptation algorithm, and the conventional LCCM gradient algorithm.