Much 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 ...
详细信息
Much 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 an
Many problems of practical significance are known to be NP-hard, and hence, are unlikelyto be solved by polynomial-time algorithms. There are several ways to cope withthe NP-hardness of a certain problem. The most pop...
详细信息
Many problems of practical significance are known to be NP-hard, and hence, are unlikely
to be solved by polynomial-time algorithms. There are several ways to cope with
the NP-hardness of a certain problem. The most popular approaches include heuristic
algorithms, approximation algorithms, and randomized algorithms. Recently, parameterizedcomputation and complexity have been receiving a lot of attention. By
taking advantage of small or moderate parameter values, parameterized algorithms
provide new venues for practically solving problems that are theoretically intractable.
In this dissertation, we design efficient parameterized algorithms for several wellknown
NP-hard problems and prove strong lower bounds for some others. In doing
so, we place emphasis on the development of new techniques that take advantage of
the structural properties of the problems.
We present a simple parameterized algorithm for Vertex Cover that uses polynomial
space and runs in time O(1.2738k + kn). It improves both the previous
O(1.286k + kn)-time polynomial-space algorithm by Chen, Kanj, and Jia, and the
very recent O(1.2745kk4 + kn)-time exponential-space algorithm, by Chandran and
Grandoni. This algorithm stands out for both its performance and its simplicity. Essential
to the design of this algorithm are several new techniques that use structural
information of the underlying graph to bound the search space.
For Vertex Cover on graphs with degree bounded by three, we present a still better algorithm that runs in time O(1.194k + kn), based on an âÂÂalmost-globalâÂÂ
analysis of the search tree.
We also show that an important structural property of the underlying graphs âÂÂ
the graph genus â largely dictates the computational complexity of some important
graph problems including Vertex Cover, Independent Set and Dominating Set.
We present a set of new techniques that allows us to prove almost tight computational
lower bounds for some NP-hard problems, such as Clique, Dominat
Background: Structure matching plays an important part in understanding the functional role of biological structures. Bioinformatics assists in this effort by reformulating this process into a problem of finding a max...
详细信息
Background: Structure matching plays an important part in understanding the functional role of biological structures. Bioinformatics assists in this effort by reformulating this process into a problem of finding a maximum common subgraph between graphical representations of these structures. Among the many different variants of the maximum common subgraph problem, the maximum common induced subgraph of two graphs is of special interest. Results: Based on current research in the area of parameterized computation, we derive a new lower bound for the exact algorithms of the maximum common induced subgraph of two graphs which is the best currently known. Then we investigate the upper bound and design techniques for approaching this problem, specifically, reducing it to one of finding a maximum clique in the product graph of the two given graphs. Considering the upper bound result, the derived lower bound result is asymptotically tight. Conclusion: parameterized computation is a viable approach with great potential for investigating many applications within bioinformatics, such as the maximum common subgraph problem studied in this paper. With an improved hardness result and the proposed approaches in this paper, future research can be focused on further exploration of efficient approaches for different variants of this problem within the constraints imposed by real applications.
We present an improved algorithm for the Vertex Cover problem on graphs of degree bounded by 3 (3DVC). We show that the 3DVC problem can be solved in time O(1.2192(k)k), where k is the number of vertices in a minimum ...
详细信息
We present an improved algorithm for the Vertex Cover problem on graphs of degree bounded by 3 (3DVC). We show that the 3DVC problem can be solved in time O(1.2192(k)k), where k is the number of vertices in a minimum vertex cover of the graph. Our algorithm also improves previous algorithms on the Independent Set problem on graphs with degree bounded by 3. (C) 2000 John Wiley & Sons, Inc.
暂无评论