Connected dominating sets on dynamic geometric graphs

DOI10.1016/J.COMGEO.2012.01.004zbMATH Open1254.05139OpenAlexW2173066068MaRDI QIDQ691774FDOQ691774

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

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.

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)

Cites Work

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

Cited In (4)

• 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
• Title not available (Why is that?)

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)