Connected dominating sets on dynamic geometric graphs

DOI10.1016/j.comgeo.2012.01.004zbMath1254.05139OpenAlexW2173066068MaRDI QIDQ691774

Arik Motskin, Nikola Milosavljević, Leonidas J. Guibas

Publication date: 4 December 2012

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2012.01.004

zbMATH Keywords

lower boundbichromatic closest pair queriesdynamic graphgeometric distanceminimum connected dominating set (MCDS)randomized algotithmsrange searching queriesunit-ball graph

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (1)

Unnamed Item

Cites Work

• Unnamed Item
• Unit disk graphs
• Euclidean minimum spanning trees and bichromatic closest pairs
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Approximation algorithms for connected dominating sets
• Geometry Helps in Matching
• Adding range restriction capability to dynamic data structures
• Data Structures for Mobile Data
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Discrete mobile centers
• Smooth kinetic maintenance of clusters
• Optimal strategies of the search for an extremum
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Connected dominating sets on dynamic geometric graphs