Comparison of Two CDS Algorithms on Random Unit Ball Graphs
Explore this paper's citation graph
Summary
This paper compares asymptotic “average case”performance of two closely related algorithms for finding small connected dominating sets and concludes that the latter performance is optimal insofar as the minimum connected dominating set also has Θ(`n) vertices ’on average’.
- Type
- article
- Published
- 2005-01-01
- Cited by
- 10
- References
- 44
- OpenAlex
- https://openalex.org/W55142848
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:892530
Keywords
Combinatorics, Mathematics, Unit cube, Random graph, Dominating set
References
- Analytical results on Connected dominating sets in mobile ad hoc networks
- Connected Domination in Multihop Ad Hoc Wireless Networks
- Computing Connected Dominated Sets with Multipoint Relays
- Spine routing in ad hoc networks
- Simple heuristics for unit disk graphs
- The Expected Size of the Rule k Dominating Set
- Distributed heuristics for connected dominating sets in wireless ad hoc networks
- Internets in the sky: The capacity of three-dimensional wireless networks
- Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks
- The Broadcast Storm Problem in a Mobile Ad Hoc Network
- Comparison of broadcasting techniques for mobile ad hoc networks
- On calculating connected dominating set for efficient routing in ad hoc wireless networks
- Frequency assignment: Theory and applications
- The Maximum Vertex Degree of a Graph on Uniform Points in [0, 1] d
- Unit disk graphs
- Planar Formulae and Their Uses
- Random Plane Networks
- Routing in ad-hoc networks using minimum connected dominating sets
- Performance analysis of broadcast protocols in ad hoc networks based on self-pruning
- On the reduction of broadcast redundancy in mobile ad hoc networks
Cited by
- A better approximation for constructing virtual backbone in 3D wireless ad-hoc networks
- Energy-efficient topology control for three-dimensional sensor networks
- Connected dominating set algorithms for wireless sensor networks
- Covering random points in a unit disk
- A Better Approximation Algorithm for Computing Connected Dominating Sets in Unit Ball Graphs
- On Constructing Strongly Connected Dominating and Absorbing Set in 3-Dimensional Wireless Ad Hoc Networks
- Performance Analysis and Improvement for the Construction of MCDS Problem in 3D Space
- Connected Dominating Set in Wireless Networks
- Topology Control and Geometric Routing for Wireless Ad Hoc Networks
Related papers
- A LOCAL Constant Approximation Factor Algorithm for Minimum Dominating Set of Certain Planar Graphs
- Minimal Dominating Sets in a Tree: Counting, Enumeration, and Extremal Results
- Exact Algorithms for Edge Domination
- Improved Approximation Bounds for Edge Dominating Set in Dense Graphs
- Complexity of Computation of Dominating Sets in Geo-Mathmetics Algorithm : A Review