Connected Dominating Set: Theory and Applications

Cover......Page 1
Connected Dominating Set:Theory and Applications......Page 4
Preface......Page 6
Contents......Page 8
1.1 Connected Domination Number......Page 11
1.2 Virtual Backbone in Wireless Networks......Page 13
1.3 Converter Placement in Optical Networks......Page 15
1.4 Connected Domatic Number......Page 16
1.5 Lifetime of Sensor Networks......Page 18
1.6 Theory and Applications......Page 19
2.1 Motivation and Overview......Page 20
2.2 Complexity of Approximation......Page 22
2.3 Two-Stage Greedy Approximation......Page 23
2.4 Weakly CDS......Page 26
2.5 One-Stage Greedy Approximation......Page 29
2.6 Weighted CDS......Page 38
2.7 Directed CDS......Page 42
3.1 Motivation and Overview......Page 44
3.2 NP-Hardness and PTAS......Page 46
3.3 Two-Stage Algorithm......Page 53
3.4 Independent Number (I)......Page 56
3.5 Independent Number (II)......Page 63
3.6 Zassenhaus–Groemer–Oler Inequality......Page 66
4.1 Motivation and Overview......Page 72
4.2 Gregory–Newton Problem......Page 73
4.3 Independent Points in Two Balls......Page 76
4.4 Growth-Bounded Graphs......Page 78
4.5 PTAS in Growth-Bounded Graphs......Page 82
5.1 Motivation and Overview......Page 85
5.2 Node-Weighted Steiner Tree......Page 86
5.3 Double Partition......Page 88
5.4 Cell Decomposition......Page 90
5.5 6-Approximation......Page 94
5.6 4-Approximation......Page 100
5.7 3.63-Approximation......Page 104
6.1 Motivation and Overview......Page 113
6.2 Max-Lifetime Connected Coverage......Page 115
6.3 Domatic Partition......Page 121
6.4 Min-Weight Dominating Set......Page 125
7.1 Motivation and Overview......Page 127
7.2 Complexity in General Graphs......Page 129
7.3 CDS with Constraint (ROC1)......Page 132
7.4 CDS with Constraint (ROCα) for α≥5......Page 133
8.1 Motivation and Overview......Page 140
8.2 Local Independence Number......Page 141
8.4 Greedy Approximation for Min-CDS......Page 153
9.1 Motivation and Overview......Page 157
9.2 Voronoi Diagram and Dual of Disks......Page 158
9.3 Local Search for Min-DS......Page 161
9.4 A Two-Staged Algorithm for Min-CDS......Page 165
10.2 Minimum Geometric Hitting Set......Page 166
10.3 Minimum Disk Cover......Page 170
11.1 Motivation and Overview......Page 173
11.2 Geometric Preliminaries......Page 175
11.3 Dominating Tree......Page 178
11.4 Broadcast Scheduling......Page 181
11.5 Aggregation Scheduling......Page 182
11.6 Gathering Scheduling......Page 183
11.7 Gossiping Scheduling......Page 185
12.1 Motivation and Overview......Page 187
12.2 Preliminaries......Page 188
12.3 Algorithm Description......Page 189
12.4 Performance Analysis......Page 191
References......Page 196
Index......Page 203