Dominating sets and connected dominating sets in dynamic graphs
From MaRDI portal
Recommendations
Cites work
- A data structure for dynamic trees
- A deamortization approach for dynamic spanner and dynamic maximal matching
- A Greedy Heuristic for the Set-Covering Problem
- A new approach to dynamic all pairs shortest paths
- A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
- A threshold of ln n for approximating set cover
- An efficient distributed algorithm for constructing small dominating sets
- Approximation algorithms for connected dominating sets
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Connected dominating set. Theory and applications
- Connected dominating sets on dynamic geometric graphs
- Constant-time distributed dominating set approximation
- Deterministic fully dynamic data structures for vertex cover and matching
- Faster fully dynamic matchings with small approximation ratios
- Fully Dynamic Maximal Independent Set with Sublinear in n Update Time
- Fully dynamic maximal independent set with sublinear update time
- scientific article; zbMATH DE number 3702724 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 6850309 (Why is no real title available?)
- Online and dynamic algorithms for set cover
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Strong lower bounds on the approximability of some NPO PB-complete maximization problems
Cited in
(6)- A heuristic approximation algorithm of minimum dominating set based on rough set theory
- scientific article; zbMATH DE number 1472178 (Why is no real title available?)
- Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set
- Fully dynamic sequential and distributed algorithms for MAX-CUT
- Connected dominating sets on dynamic geometric graphs
- Online landmark replacement for out-of-sample dimensionality reduction methods
This page was built for publication: Dominating sets and connected dominating sets in dynamic graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090485)
