Custom cover image
Connected Dominating Set: Theory and Applications / by Ding-Zhu Du, Peng-Jun Wan
Contributor(s): Resource type: Ressourcentyp: Buch (Online)Book (Online)Language: English Series: Springer Optimization and Its Applications ; 77 | SpringerLink BücherPublisher: New York, NY : Springer, 2013Description: Online-Ressource (IX, 203 p. 72 illus., 6 illus. in color, digital)ISBN:- 9781461452423
- Funknetz
- Netzwerk Graphentheorie
- Dominanzprinzip
- Extremalproblem
- Algorithmische Geometrie
- Komplexität
- Algorithmus
- Mathematics
- Computer Communication Networks
- Computer software
- Algorithms
- Operations research
- Computer communication systems
- Management science
- Combinatorics
- Mathematical optimization
- Graph theory
- Domination (Graph theory)
- 519.6
- QA402-402.37 T57.6-57.97
- QA402-402.37
- T57.6-57.97
Contents:
Summary: The connected dominating set (CDS) has been a classic subject studied in graph theory since 1975. It has been discovered in recent years that CDS has important applications in communication networks —especially in wireless networks —as a virtual backbone. Motivated from those applications, many papers have been published in the literature during last 15 years. Now, the connected dominating set has become a hot research topic in computer science. This work is a valuable reference for researchers in computer science and operations research, especially in areas of theoretical computer science, computer communication networks, combinatorial optimization, industrial engineering, and discrete mathematics. The book may also be used as a text in a graduate seminar for PhD students. Readers should have a basic knowledge of computational complexity and combinatorial optimization. In this book, the authors present the state-of-the-art in the study of connected dominating sets. Each chapter is devoted to one problem, and consists of three parts: motivation and overview, problem complexity analysis, and approximation algorithm designs. The text is designed to give the reader a clear understanding of the background, formulation, existing important research results, and open problems. Topics include minimum CDS, routing-cost constrained CDS, weighted CDS, directed CDS, SCDS (strongly connected dominating set), WCDS (weakly connected dominating set), CDS-partition, virtual backbone in wireless networks, convertor placement in optical networks, coverage in wireless sensor networks, and more.PPN: PPN: 1651891206Package identifier: Produktsigel: ZDB-2-SEB | ZDB-2-SXMS | ZDB-2-SMA
Connected Dominating Set:Theory and Applications; Preface; Contents; Chapter1 Introduction; 1.1 Connected Domination Number; 1.2 Virtual Backbone in Wireless Networks; 1.3 Converter Placement in Optical Networks; 1.4 Connected Domatic Number; 1.5 Lifetime of Sensor Networks; 1.6 Theory and Applications; Chapter2 CDS in General Graph; 2.1 Motivation and Overview; 2.2 Complexity of Approximation; 2.3 Two-Stage Greedy Approximation; 2.4 Weakly CDS; 2.5 One-Stage Greedy Approximation; 2.6 Weighted CDS; 2.7 Directed CDS; Chapter3 CDS in Unit Disk Graph; 3.1 Motivation and Overview
3.2 NP-Hardness and PTAS3.3 Two-Stage Algorithm; 3.4 Independent Number (I); 3.5 Independent Number (II); 3.6 Zassenhaus-Groemer-Oler Inequality; Chapter 4 CDS in Unit Ball Graphs and Growth Bounded Graphs; 4.1 Motivation and Overview; 4.2 Gregory-Newton Problem; 4.3 Independent Points in Two Balls; 4.4 Growth-Bounded Graphs; 4.5 PTAS in Growth-Bounded Graphs; Chapter5 Weighted CDS in Unit Disk Graph; 5.1 Motivation and Overview; 5.2 Node-Weighted Steiner Tree; 5.3 Double Partition; 5.4 Cell Decomposition; 5.5 6-Approximation; 5.6 4-Approximation; 5.7 3.63-Approximation; Chapter6 Coverage
6.1 Motivation and Overview6.2 Max-Lifetime Connected Coverage; 6.3 Domatic Partition; 6.4 Min-Weight Dominating Set; Chapter7 Routing-Cost Constrained CDS; 7.1 Motivation and Overview; 7.2 Complexity in General Graphs; 7.3 CDS with Constraint (ROC1); 7.4 CDS with Constraint (ROCα) for α≥5; Chapter8 CDS in Disk-Containment Graphs; 8.1 Motivation and Overview; 8.2 Local Independence Number; 8.3 Independence Number; 8.4 Greedy Approximation for Min-CDS; Chapter 9 CDS in Disk-Intersection Graphs; 9.1 Motivation and Overview; 9.2 Voronoi Diagram and Dual of Disks; 9.3 Local Search for Min-DS
9.4 A Two-Staged Algorithm for Min-CDSChapter10 Geometric Hitting Set and Disk Cover; 10.1 Motivation and Overview; 10.2 Minimum Geometric Hitting Set; 10.3 Minimum Disk Cover; Chapter11 Minimum-Latency Scheduling; 11.1 Motivation and Overview; 11.2 Geometric Preliminaries; 11.3 Dominating Tree; 11.4 Broadcast Scheduling; 11.5 Aggregation Scheduling; 11.6 Gathering Scheduling; 11.7 Gossiping Scheduling; Chapter12 CDS in Planar Graphs; 12.1 Motivation and Overview; 12.2 Preliminaries; 12.3 Algorithm Description; 12.4 Performance Analysis; References; Index;
No physical items for this record