Browsing by Subject "Graph theory"
Now showing 1 - 11 of 11
Results Per Page
Sort Options
Item 3D face recognition with wireless transportation(2009-05-15) Zou, LeIn this dissertation, we focus on two related parts of a 3D face recognition system with wireless transportation. In the ?rst part, the core components of the system, namely, the feature extraction and classi?cation component, are introduced. In the feature extraction component, range images are taken as inputs and processed in order to extract features. The classi?cation component uses the extracted features as inputs and makes classi?cation decisions based on trained classi?ers. In the second part, we consider the wireless transportation problem of range images, which are captured by scattered sensor nodes from target objects and are forwarded to the core components (i.e., feature extraction and classi?cation components) of the face recognition system. Contrary to the conventional de?nition of being a transducer, a sensor node can be a person, a vehicle, etc. The wireless transportation component not only brings ?exibility to the system but also makes the ?proactive? face recognition possible. For the feature extraction component, we ?rst introduce the 3D Morphable Model. Then a 3D feature extraction algorithm based on the 3D Morphable Model is presented. The algorithm is insensitive to facial expression. Experimental results show that it can accurately extract features. Following that, we discuss the generic face warping algorithm that can quickly extract features with high accuracy. The proposed algorithm is robust to holes, facial expressions and hair. Furthermore, our experimental results show that the generated features can highly di?erentiate facial images. For the classi?cation component, a classi?er based on Mahalanobis distance is introduced. Based on the classi?er, recognition performances of the extracted features are given. The classi?cation results demonstrate the advantage of the features from the generic face warping algorithm. For the wireless transportation of the captured images, we consider the location-based wireless sensor networks (WSN). In order to achieve e?cient routing perfor?mance, a set of distributed stateless routing protocols (PAGER) are proposed for wireless sensor networks. The loop-free and delivery-guaranty properties of the static version (PAGER-S) are proved. Then the performance of PAGER protocols are compared with other well-known routing schemes using network simulator 2 (NS2). Simulation results demonstrate the advantages of PAGER.Item A graphical user interface for the analysis of task graphs(Texas Tech University, 1999-08) Krishna, SanthoshThis thesis describes a flexible graphical user interface (GUI) tool designed and developed for the analysis of task graphs. The interface tool takes the task graph along with parameters such as execution times of the tasks, number of processors, and communication costs, as input and gives the average completion time and the probability distribution of the completion times for the task graph as output, using a numerical analysis tool and a simulation analysis tool. The interface provides access to heuristic algorithms to generate an allocation matrix that maps tasks into processors. The solution tools uses this matrix along with the parameters to generate results. The GUI is developed in such a way that the user can configure it by adding new heuristics or any other solution scheme.Item An efficient implementation of a planarity testing algorithm for a graph with constraints(Texas Tech University, 1982-08) Sun, MosesNot availableItem Analysis of the power grid: structure and secure operations(2015-08) Deka, Deepjyoti; Vishwanath, Sriram; Baldick, Ross; Kwasinski, Alexis; Meyers, Lauren A.; Moorty, SainathPower Grids form one of the vital backbone-networks of our society providing electricity for daily socio-economic activities. Given its importance, there is a greater need to understand the structure and control of the power grid for fair power market computations and efficient delivery of electricity. This work studies two problems associated with different aspects of today's power grid network and combines techniques from network science, control theory and optimization to analyze them. The first problem relates to understanding the common structural features observed in several power grids across the world and developing a trackable modeling framework that incorporates these features. Such a framework can lead to insights on structural vulnerability of the grid and help design realistic test cases to study effects of structural and operational reinforcements as the grid evolves with time. We develop a generative model based on spatial point process theory that provably produces the distinct exponential degree distribution observed in several power grids. Further, critical graph parameters like diameter, eigen-spread, betweenness centralities and clustering coefficients are used to compare the performance of our framework in modeling the power grids in Western USA and under ERCOT in Texas. The second problem discussed here involves a detailed study of malicious data attacks on state estimation in the power grid. Such data attacks pose a serious threat to efforts related to implementing distributed control for efficient operations in the grid. We develop a graph-theoretic framework to analyze the design of optimal data attacks and study cost-optimal techniques to build resilience against them. The study involves attacks by a practical adversary capable of modifying meter readings as well as of jamming the flow of information from meters to the grid controller. We prove that the design of optimal `hidden' and `detectable' attacks can be formulated as constrained graph-cut problems that depend on the relative costs of adversarial techniques, and present algorithms for attack construction. Further, we design a new `topology' attack regime where an adversary changes beaker statuses of grid lines to affect state estimation in systems where all meter measurements are encrypted and hence secure from manipulation. We discuss bounds on the security requirements imposed by the developed attack models and design algorithms for determining the optimal protection strategy. This helps present an accurate characterization of grid vulnerability to general data attacks and eavesdroppers and motivates efforts to expand the presence of new secure meters to foil cyber attacks in the grid.Item Item Efficient drawing of partially oriented planar graphs with application to the circuit layout problem(Texas Tech University, 1985-05) Hanna, James ArthurNot availableItem Essays on mechanism design, safety, and crime(2014-05) Shoukry, George Fouad Nabih; Abrevaya, Jason; Stinchcombe, MaxwellThis dissertation uses theoretical and empirical tools to answer applied questions of design with an emphasis on issues relating to safety and crime. The first essay incorporates safety in implementation theory and studies when and how safe mechanisms can be designed to obtain socially desirable outcomes. I provide general conditions under which a social choice rule can be implemented using safe mechanisms. The second essay is an empirical study of how criminals respond to changing profitability of crime, a question that informs the policy debate on the most effective crime fighting methods. I find that the price elasticity of theft is about 1 in the short term and increases to about 1.2 over a seven-month horizon, suggesting that policies that directly affect crime profitability, such as policies that shut down black markets or those that reduce demand for illegal goods, can be relatively effective. The third essay shows that any standard implementation problem can be formulated as a question about the existence of a graph that solves a graph coloring problem, establishing a connection between implementation theory and graph theory. More generally, an implementation problem can be viewed as a constraint satisfaction problem, and I propose an algorithm to design simple mechanisms to solve arbitrary implementation problems.Item Graph-theoretic methods for determining the distinguished eigenvalues to nonnegative reducible matrices with applications to certain linear systems(Texas Tech University, 1986-08) Beasley, John C.The proposed research consists of designing an algorithm, or computational procedure, for determining the distinguished eigenvalues of a nonnegative, nonnull reducible matrix. Nonnegative reducible matrices are those containing nonnegative entries, and are usually represented in upper triangular block form (to which they can be converted by a sequence of permutation transformations). The diagonal blocks in such a representation are either 1 x 1—null matrices or nonnegative irreducible matrices (which do not admit such a "triangular" deconposition). Distinguished eigenvalues are those nonnegative eigenvalues which have an associated nonnegative eigenvector. The algorithm will incorporate the graph-theoretic results of H. Dean Victory, Jr., and the numerical results of W. Bunse, B. Schulzendorff, L. Eisner, and Pham van At on the computation of the dominant eigenvalue, with normalized eigenvector, for nonnegative irreducible matrices. The results of this thesis can then be applied to con5)uting nonnegative solutions X to conditional equations of the form Xx = Ax + b where X is a positive parameter, b a nontrivial vector given with nonnegative components, A a nontrivial and nonnegative matrix.Item ProGENitor : an application to guide your career(2014-12) Hauptli, Erich Jurg; Aziz, AdnanThis report introduces ProGENitor; a system to empower individuals with career advice based on vast amounts of data. Specifically, it develops a machine learning algorithm that shows users how to efficiently reached specific career goals based upon the histories of other users. A reference implementation of this algorithm is presented, along with experimental results that show that it provides quality actionable intelligence to users.Item Systematic generation and evaluation of stochastic petri net models for the performance analysis of task graphs(Texas Tech University, 1995-05) Decker, Jeffrey FloydThe main thrust of this work is to develop a mechanism to generate a Stochastic Petri Net from a given task graph. The task graph corresponds to a particular job that has been broken down into several tasks. The problem is to find the average completion time of any job represented by a task graph using an unlimited number of processors as v^ell as a limited number of processors. Currently, there are models that solve the problem for an unlimited number of processors [10]. However, there is no model available to solve this problem for a limited number of processors. Work has been done using Queuing Networks [13], but not Stochastic Petri Nets. To analyze a particular task graph using a Petri Net with a limited number of processors, the Stochastic Petri Net(SPN) model must be generated manually. Once the Stochastic Petri Net is generated, its evaluation can be carried out using a tool such as the Stochastic Petri Net Package (SPNP) [1] developed at Duke University.Item