Browsing by Subject "complexity"
Now showing 1 - 3 of 3
Results Per Page
Sort Options
Item Effective algorithms and protocols for wireless networking: a topological approach(Texas A&M University, 2008-10-10) Zhang, FenghuiMuch research has been done on wireless sensor networks. However, most protocols and algorithms for such networks are based on the ideal model Unit Disk Graph (UDG) model or do not assume any model. Furthermore, many results assume the knowledge of location information of the network. In practice, sensor networks often deviate from the UDG model significantly. It is not uncommon to observe stable long links that are more than five times longer than unstable short links in real wireless networks. A more general network model, the quasi unit-disk graph (quasi-UDG) model, captures much better the characteristics of wireless networks. However, the understanding of the properties of general quasi-UDGs has been very limited, which is impeding the design of key network protocols and algorithms. In this dissertation we study the properties for general wireless sensor networks and develop new topological/geometrical techniques for wireless sensor networking. We assume neither the ideal UDG model nor the location information of the nodes. Instead we work on the more general quasi-UDG model and focus on figuring out the relationship between the geometrical properties and the topological properties of wireless sensor networks. Based on such relationships we develop algorithms that can compute useful substructures (planar subnetworks, boundaries, etc.). We also present direct applications of the properties and substructures we constructed including routing, data storage, topology discovery, etc. We prove that wireless networks based on quasi-UDG model exhibit nice properties like separabilities, existences of constant stretch backbones, etc. We develop efficient algorithms that can obtain relatively dense planar subnetworks for wireless sensor networks. We also present efficient routing protocols and balanced data storage scheme that supports ranged queries. We present algorithmic results that can also be applied to other fields (e.g., information management). Based on divide and conquer and improved color coding technique, we develop algorithms for path, matching and packing problem that significantly improve previous best algorithms. We prove that it is unlikely for certain problems in operation science and information management to have any relatively effective algorithm or approximation algorithm for them.Item Mathematical Foundations and Algorithms for Clique Relaxations in Networks(2012-02-14) Pattillo, JeffreyThis dissertation establishes mathematical foundations for the properties exhibited by generalizations of cliques, as well as algorithms to find such objects in a network. Cliques are a model of an ideal group with roots in social network analysis. They have since found applications as a part of grouping mechanisms in computer vision, coding theory, experimental design, genomics, economics, and telecommunications among other fields. Because only groups with ideal properties form a clique, they are often too restrictive for identifying groups in many real-world networks. This motivated the introduction of clique relaxations that preserve some of the various defining properties of cliques in relaxed form. There are six clique relaxations that are the focus of this dissertation: s-clique, s-club, s-plex, k-core, quasi-clique, and k-connected subgraphs. Since cliques have found applications in so many fields, research into these clique relaxations has the potential to steer the course of much future research. The focus of this dissertation is on bringing organization and rigorous methodology to the formation and application of clique relaxations. We provide the first taxonomy focused on how the various clique relaxations relate on key structural properties demonstrated by groups. We also give a framework for how clique relaxations can be formed. This equips researchers with the ability to choose the appropriate clique relaxation for an application based on its structural properties, or, if an appropriate clique relaxation does not exist, form a new one. In addition to identifying the structural properties of the various clique relaxations, we identify properties and prove propositions that are important computationally. These assist in creating algorithms to find a clique relaxation quickly as it is immersed in a network. We give the first ever analysis of the computational complexity of finding the maximum quasi-clique in a graph. Such analysis identifies for researchers the appropriate set of computational tools to solve the maximum quasiclique problem. We further create a polynomial time algorithm for identifying large 2-cliques within unit disk graphs, a special class of graphs often arising in communication networks. We prove the algorithm to have a guaranteed 1=2-approximation ratio and finish with computational results.Item Small-world characteristics in geographic, epidemic, and virtual spaces : a comparative study(Texas A&M University, 2007-09-17) Xu, ZengwangThis dissertation focuses on a comparative study of small-world characteristics in geographical, epidemic, and virtual spaces. Small-world network is the major component of the ??????new science of networks?????? that emerged recently in research related to complex networks. It has shown a great potential to model the complex networks encountered in geographical studies. This dissertation, in an attempt to understand the emergence of small-world phenomenon in spatial networks, has investigated the smallworld properties in aforementioned three spaces. Specifically, this dissertation has studied roadway transportation networks at national, metropolitan, and intra-city scales via network autocorrelation methods to investigate the distance effect on the emergence of small-world properties. This dissertation also investigated the effect of small-world network properties on the epidemic diffusion and different control strategies through agent-based simulation on social networks. The ASLevel Internet in the contiguous U.S. has been studied in its relation between local and global connections, and its correspondence with small-world characteristics. Through theoretical simulations and empirical studies on spatial networks, this dissertation has contributed to network science with a new method ?????? network autocorrelation, and better understanding from the perspective of the relation between local and global connections and the distance effect in networks. A small-world phenomenon results from the interplay between the dynamics occurring on networks and the structure of networks; when the influencing distance of the dynamics reaches to the threshold of the network, the network will logically emerge as a small-world network. With the aid of numerical simulation a small-world network has a large number of local connections and a small number of global links. It is also found that the epidemics will take shorter time period to reach largest size on a small-world network and only particular control strategy, such as targeted control strategy, will be effective on smallworld networks. This dissertation bridges the gap between new science of networks and the network study in geography. It potentially contributes to GIScience with new modeling strategy for representing, analyzing, and modeling complexity in hazards prevention, landscape ecology, and sustainability science from a network-centric perspective.