[{"publication":"Algorithmica","title":"Deterministic dynamic matching in O(1) update time","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00453-019-00630-4"}],"issue":"4","scopus_import":"1","citation":{"ieee":"S. Bhattacharya, D. Chakrabarty, and M. H. Henzinger, “Deterministic dynamic matching in O(1) update time,” <i>Algorithmica</i>, vol. 82, no. 4. Springer Nature, pp. 1057–1080, 2020.","chicago":"Bhattacharya, Sayan, Deeparnab Chakrabarty, and Monika H Henzinger. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>. Springer Nature, 2020. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>.","ama":"Bhattacharya S, Chakrabarty D, Henzinger MH. Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. 2020;82(4):1057-1080. doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>","mla":"Bhattacharya, Sayan, et al. “Deterministic Dynamic Matching in O(1) Update Time.” <i>Algorithmica</i>, vol. 82, no. 4, Springer Nature, 2020, pp. 1057–80, doi:<a href=\"https://doi.org/10.1007/s00453-019-00630-4\">10.1007/s00453-019-00630-4</a>.","short":"S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, Algorithmica 82 (2020) 1057–1080.","ista":"Bhattacharya S, Chakrabarty D, Henzinger MH. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080.","apa":"Bhattacharya, S., Chakrabarty, D., &#38; Henzinger, M. H. (2020). Deterministic dynamic matching in O(1) update time. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00453-019-00630-4\">https://doi.org/10.1007/s00453-019-00630-4</a>"},"page":"1057-1080","oa_version":"Published Version","publication_status":"published","day":"01","abstract":[{"text":"We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm’s past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of (2+ε) and an amortized update time of O(logn/ε2). Our result can be generalized to give a fully dynamic O(f3)-approximate algorithm with O(f2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices.","lang":"eng"}],"status":"public","date_updated":"2022-09-12T08:55:46Z","article_type":"original","volume":82,"month":"04","quality_controlled":"1","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"extern":"1","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","keyword":["Dynamic algorithms","Data structures","Graph algorithms","Matching","Vertex cover"],"intvolume":"        82","date_created":"2022-07-27T14:31:06Z","date_published":"2020-04-01T00:00:00Z","author":[{"full_name":"Bhattacharya, Sayan","first_name":"Sayan","last_name":"Bhattacharya"},{"last_name":"Chakrabarty","full_name":"Chakrabarty, Deeparnab","first_name":"Deeparnab"},{"orcid":"0000-0002-5008-6530","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","full_name":"Henzinger, Monika H","first_name":"Monika H"}],"oa":1,"_id":"11675","type":"journal_article","language":[{"iso":"eng"}],"doi":"10.1007/s00453-019-00630-4","publisher":"Springer Nature","year":"2020"},{"_id":"11679","author":[{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","first_name":"Monika H","full_name":"Henzinger, Monika H"},{"full_name":"King, V.","first_name":"V.","last_name":"King"},{"last_name":"Warnow","first_name":"T.","full_name":"Warnow, T."}],"date_published":"1999-05-01T00:00:00Z","year":"1999","publisher":"Springer Nature","doi":"10.1007/pl00009268","language":[{"iso":"eng"}],"type":"journal_article","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"quality_controlled":"1","month":"05","article_type":"original","volume":24,"date_created":"2022-07-27T15:02:28Z","intvolume":"        24","keyword":["Algorithms","Data structures","Evolutionary biology","Theory of databases"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","article_processing_charge":"No","abstract":[{"lang":"eng","text":"We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each T i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n }, we let T|L denote the minimal subtree of T induced by the nodes of L and all their ancestors. The consensus tree problem asks whether there exists a tree T * such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present algorithms which test if a given set of trees has a consensus tree and if so, construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n 2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes time O(N log3 n) and uses linear space. The previous best for this problem was a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then, after each batch, either find a new component that has just been created or determine that there is no such component. For this problem, we have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n }), where b 0 is the number of batches which do not result in a new component. For our particular application, b0≤1 . If all edges are deleted, then the best previously known deterministic algorithm requires time O(mn−−√) to solve this problem. We also present two applications of these consensus tree algorithms which solve other problems in computational evolutionary biology."}],"day":"01","oa_version":"None","page":"1-13","publication_status":"published","date_updated":"2023-02-21T16:33:24Z","status":"public","title":"Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology","related_material":{"record":[{"relation":"earlier_version","id":"11927","status":"public"}]},"publication":"Algorithmica","citation":{"ieee":"M. H. Henzinger, V. King, and T. Warnow, “Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology,” <i>Algorithmica</i>, vol. 24. Springer Nature, pp. 1–13, 1999.","chicago":"Henzinger, Monika H, V. King, and T. Warnow. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>. Springer Nature, 1999. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>.","ama":"Henzinger MH, King V, Warnow T. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. 1999;24:1-13. doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>","ista":"Henzinger MH, King V, Warnow T. 1999. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. Algorithmica. 24, 1–13.","apa":"Henzinger, M. H., King, V., &#38; Warnow, T. (1999). Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009268\">https://doi.org/10.1007/pl00009268</a>","short":"M.H. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.","mla":"Henzinger, Monika H., et al. “Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology.” <i>Algorithmica</i>, vol. 24, Springer Nature, 1999, pp. 1–13, doi:<a href=\"https://doi.org/10.1007/pl00009268\">10.1007/pl00009268</a>."},"scopus_import":"1"}]