Leicester Research Archive

Leicester Research Archive >
College of Science and Engineering >
Computer Science, Department of >
Theses, Dept. of Computer Science >

Please use this identifier to cite or link to this item: http://hdl.handle.net/2381/10837

Title: Approximating Node-Weighted Steiner Subgraphs for Multicast Communication in Wireless Networks
Authors: Shahnaz, Ambreen
Supervisors: Erlebach, Thomas
Fung, Ping
Award date: 1-Feb-2012
Presented at: University of Leicester
Abstract: We are motivated by the problem of computing multicast routing structures in wireless ad-hoc networks modelled by special classes of graphs including unit disk graphs, quasi-unit disk graphs and (λ + 1)-claw-free graphs. Multicast communication can be established by a tree known as Steiner tree. Wireless ad-hoc networks must operate using limited resources, therefore, the suitability of nodes for inclusion in a Steiner tree can vary widely between different nodes. We model this by assuming that each node of the network is assigned a weight that represents the cost of including it in the Steiner tree. Our goal is to compute a Steiner tree with minimum total node weight. However, in scenarios where nodes and links are not reliable, a tree has the drawback that it can be disconnected by the failure of even a single link or node in the network. Therefore, we also consider various fault-tolerant routing structures called 2-edge-connected Steiner subgraphs, k-edge-connected Steiner subgraphs, 2-vertex-connected Steiner subgraphs, and 2-edge-connected group Steiner subgraphs. The problems we consider are NP-hard, so we are interested in algorithms that compute provably good approximate solutions in polynomial time. We present a generalization of Steiner subgraph problems referred to as the node-weighted δ-Steiner subgraph problem, where δ represents connectivity requirements. We present an algorithm with approximation ratio 0.5dρ for the node-weighted δ-Steiner subgraph problem, where d is the bounded maximum degree of the solution subgraph, and ρ is the approximation ratio of the edge-weighted version of the δ-Steiner subgraph problem. We then shown how to construct solution subgraphs of bounded maximum degree d in several graph classes for our problem variants. As a result, we obtain algorithms for the problems we consider, on graph classes that admit subgraphs of small degree, whose approximation ratios are better than the best known ratios for the same problems on general graphs.
Links: http://hdl.handle.net/2381/10837
Type: Thesis
Level: Doctoral
Qualification: PhD
Rights: Copyright © the author, 2012
Appears in Collections:Leicester Theses
Theses, Dept. of Computer Science

Files in This Item:

File Description SizeFormat
2012ShahnazAphd.pdf629.19 kBAdobe PDFView/Open
View Statistics

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.