Fully Dynamic Set Cover-Improved and Simple, 2018. ,
Fully dynamic maximal independent set with sublinear update time, Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, 2018. ,
Fully Dynamic Maximal Independent Set with Sublinear in n Update Time, pp.1919-1936, 2019. ,
,
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1899-1918, 2019. ,
Faster fully dynamic matchings with small approximation ratios, Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp.692-711, 2016. ,
Routing in ad-hoc networks using a virtual backbone, Proceedings of the 6th International Conference on Computer Communications and Networks (IC3N'97), pp.1-20, 1997. ,
Dynamic algorithms for graph coloring, Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp.1-20, 2018. ,
Deterministic fully dynamic data structures for vertex cover and matching, SIAM Journal on Computing, vol.47, issue.3, pp.859-887, 2018. ,
A new heuristic for the minimum connected dominating set problem on ad hoc wireless networks, Recent developments in cooperative control and optimization, pp.61-73, 2004. ,
A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks, Networks: An International Journal, vol.42, issue.4, pp.202-208, 2003. ,
A Greedy Heuristic for the Set-Covering Problem, Mathematics of Operations Research, vol.4, issue.3, pp.233-235, 1979. ,
A New Approach to Dynamic All Pairs Shortest Paths, J. ACM, vol.51, issue.6, pp.968-992, 2004. ,
Connected dominating set: theory and applications, vol.77, 2012. ,
A threshold of ln n for approximating set cover, Journal of the ACM (JACM), vol.45, issue.4, pp.634-652, 1998. ,
Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979. ,
Approximation algorithms for connected dominating sets, Algorithmica, vol.20, issue.4, pp.374-387, 1998. ,
Connected dominating sets on dynamic geometric graphs, Computational Geometry, vol.46, issue.2, pp.160-172, 2013. ,
Online and dynamic algorithms for set cover, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp.537-550, 2017. ,
Simple dynamic algorithms for Maximal Independent Set and other problems, 2018. ,
Fully dynamic (1+ e)-approximate matchings, Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pp.548-557, 2013. ,
Clique is hard to approximate withinn 1-?, Acta Mathematica, vol.182, issue.1, pp.105-142, 1999. ,
Poly-logarithmic Deterministic Fullydynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-edge, and Biconnectivity, J. ACM, vol.48, issue.4, pp.723-760, 2001. ,
An efficient distributed algorithm for constructing small dominating sets, Distributed Computing, vol.15, issue.4, p.17, 2002. ,
On the approximability of NP-complete optimization problems, 1992. ,
Constant-time distributed dominating set approximation, Distributed Computing, vol.17, issue.4, pp.303-310, 2005. ,
Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp.950-961, 2017. ,
Simple deterministic algorithms for fully dynamic maximal matching, ACM Transactions on Algorithms (TALG), vol.12, issue.1, p.7, 2016. ,
The connected domination number of a graph, J. Math. Phys, 1979. ,
A data structure for dynamic trees, Journal of computer and system sciences, vol.26, issue.3, pp.362-391, 1983. ,
Fully Dynamic Maximal Matching in Constant Update Time, 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pp.325-334, 2016. ,
On calculating connected dominating set for efficient routing in ad hoc wireless networks, Proceedings of the 3rd international workshop on Discrete algorithms and methods for mobile computing and communications, pp.7-14, 1999. ,