Connected dominating sets on dynamic geometric graphs

DOI10.1016/J.COMGEO.2012.01.004MaRDI QIDQ691774zbMATH OpenOpenAlexFDO

Authors Nikola Milosavljević, Arik Motskin, Leonidas 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

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

Recommendations

• Dominating sets and connected dominating sets in dynamic graphs
• scientific article; zbMATH DE number 1472178
• Dynamic Subgraph Connectivity with Geometric Applications
• Connected dominating set. Theory and applications
• Connected geodomination in graphs
• Connected dominating sets and a new graph invariant
• A topological approach to dynamic graph connectivity
• scientific article; zbMATH DE number 3873384
• On connected dominating sets of restricted diameter
• Dynamical \(2\)-domination in graphs.

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Adding range restriction capability to dynamic data structures
• Approximation algorithms for connected dominating sets
• Data Structures for Mobile Data
• Discrete mobile centers
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Euclidean minimum spanning trees and bichromatic closest pairs
• Geometry Helps in Matching
• Graph-Theoretic Concepts in Computer Science
• Optimal strategies of the search for an extremum
• Smooth kinetic maintenance of clusters
• Unit disk graphs

Cited in

(4)

• scientific article; zbMATH DE number 1472178 (Why is no real title available?)
• Dominating sets and connected dominating sets in dynamic graphs
• A topological approach to dynamic graph connectivity
• Efficient local search based on dynamic connectivity maintenance for minimum connected dominating set

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q691774)