[{"date_updated":"2022-09-12T08:55:46Z","citation":{"short":"S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, Algorithmica 82 (2020) 1057–1080.","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>.","ista":"Bhattacharya S, Chakrabarty D, Henzinger MH. 2020. Deterministic dynamic matching in O(1) update time. Algorithmica. 82(4), 1057–1080.","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>","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>","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>.","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."},"year":"2020","doi":"10.1007/s00453-019-00630-4","day":"01","abstract":[{"lang":"eng","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."}],"volume":82,"extern":"1","_id":"11675","scopus_import":"1","author":[{"first_name":"Sayan","last_name":"Bhattacharya","full_name":"Bhattacharya, Sayan"},{"first_name":"Deeparnab","last_name":"Chakrabarty","full_name":"Chakrabarty, Deeparnab"},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"issue":"4","publication_status":"published","article_processing_charge":"No","date_created":"2022-07-27T14:31:06Z","title":"Deterministic dynamic matching in O(1) update time","intvolume":"        82","page":"1057-1080","quality_controlled":"1","publisher":"Springer Nature","article_type":"original","date_published":"2020-04-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]},"oa":1,"main_file_link":[{"url":"https://doi.org/10.1007/s00453-019-00630-4","open_access":"1"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","publication":"Algorithmica","oa_version":"Published Version","month":"04","language":[{"iso":"eng"}],"keyword":["Dynamic algorithms","Data structures","Graph algorithms","Matching","Vertex cover"]},{"_id":"5573","has_accepted_license":"1","license":"https://creativecommons.org/publicdomain/zero/1.0/","author":[{"first_name":"Hassan","last_name":"Alhaija","full_name":"Alhaija, Hassan"},{"first_name":"Anita","last_name":"Sellent","full_name":"Sellent, Anita"},{"full_name":"Kondermann, Daniel","last_name":"Kondermann","first_name":"Daniel"},{"first_name":"Carsten","last_name":"Rother","full_name":"Rother, Carsten"}],"datarep_id":"82","oa_version":"Published Version","date_created":"2018-12-12T12:31:36Z","department":[{"_id":"VlKo"}],"article_processing_charge":"No","month":"01","title":"Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow","contributor":[{"first_name":"Paul","contributor_type":"researcher","last_name":"Swoboda","id":"446560C6-F248-11E8-B48F-1D18A9856A87"}],"file_date_updated":"2020-07-14T12:47:05Z","keyword":["graph matching","quadratic assignment problem<"],"publisher":"Institute of Science and Technology Austria","tmp":{"legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","short":"CC0 (1.0)","name":"Creative Commons Public Domain Dedication (CC0 1.0)","image":"/images/cc_0.png"},"date_updated":"2024-02-21T13:41:17Z","citation":{"chicago":"Alhaija, Hassan, Anita Sellent, Daniel Kondermann, and Carsten Rother. “Graph Matching Problems for GraphFlow – 6D Large Displacement Scene Flow.” Institute of Science and Technology Austria, 2018. <a href=\"https://doi.org/10.15479/AT:ISTA:82\">https://doi.org/10.15479/AT:ISTA:82</a>.","ieee":"H. Alhaija, A. Sellent, D. Kondermann, and C. Rother, “Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow.” Institute of Science and Technology Austria, 2018.","ama":"Alhaija H, Sellent A, Kondermann D, Rother C. Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow. 2018. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:82\">10.15479/AT:ISTA:82</a>","apa":"Alhaija, H., Sellent, A., Kondermann, D., &#38; Rother, C. (2018). Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:82\">https://doi.org/10.15479/AT:ISTA:82</a>","ista":"Alhaija H, Sellent A, Kondermann D, Rother C. 2018. Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:82\">10.15479/AT:ISTA:82</a>.","short":"H. Alhaija, A. Sellent, D. Kondermann, C. Rother, (2018).","mla":"Alhaija, Hassan, et al. <i>Graph Matching Problems for GraphFlow – 6D Large Displacement Scene Flow</i>. Institute of Science and Technology Austria, 2018, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:82\">10.15479/AT:ISTA:82</a>."},"year":"2018","date_published":"2018-01-04T00:00:00Z","type":"research_data","doi":"10.15479/AT:ISTA:82","day":"04","abstract":[{"text":"Graph matching problems for large displacement optical flow of RGB-D images.","lang":"eng"}],"oa":1,"file":[{"file_id":"5600","creator":"system","access_level":"open_access","relation":"main_file","date_updated":"2020-07-14T12:47:05Z","file_name":"IST-2018-82-v1+1_GraphFlowMatchingProblems.zip","content_type":"application/zip","date_created":"2018-12-12T13:02:34Z","file_size":1737958,"checksum":"53c17082848e12f3c2e1b4185b578208"}],"ddc":["001"],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","related_material":{"link":[{"relation":"research_paper","url":"https://doi.org/10.1007/978-3-319-24947-6_23"}]}},{"title":"Graph matching problems for annotating C. Elegans","month":"02","article_processing_charge":"No","date_created":"2018-12-12T12:31:32Z","department":[{"_id":"VlKo"}],"oa_version":"Published Version","datarep_id":"57","author":[{"first_name":"Dagmar","last_name":"Kainmueller","full_name":"Kainmueller, Dagmar"},{"first_name":"Florian","last_name":"Jug","full_name":"Jug, Florian"},{"full_name":"Rother, Carsten","first_name":"Carsten","last_name":"Rother"},{"last_name":"Meyers","first_name":"Gene","full_name":"Meyers, Gene"}],"has_accepted_license":"1","_id":"5561","publisher":"Institute of Science and Technology Austria","keyword":["graph matching","feature matching","QAP","MAP-inference"],"file_date_updated":"2020-07-14T12:47:03Z","oa":1,"abstract":[{"lang":"eng","text":"Graph matching problems as described in \"Active Graph Matching for Automatic Joint Segmentation and Annotation of C. Elegans.\" by Kainmueller, Dagmar and Jug, Florian and Rother, Carsten and Myers, Gene, MICCAI 2014. Problems are in OpenGM2 hdf5 format (see http://hciweb2.iwr.uni-heidelberg.de/opengm/) and a custom text format used by the feature matching solver described in \"Feature Correspondence via Graph Matching: Models and Global Optimization.\" by Lorenzo Torresani, Vladimir Kolmogorov and Carsten Rother, ECCV 2008, code at http://pub.ist.ac.at/~vnk/software/GraphMatching-v1.02.src.zip. "}],"day":"13","doi":"10.15479/AT:ISTA:57","type":"research_data","date_published":"2017-02-13T00:00:00Z","citation":{"apa":"Kainmueller, D., Jug, F., Rother, C., &#38; Meyers, G. (2017). Graph matching problems for annotating C. Elegans. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT:ISTA:57\">https://doi.org/10.15479/AT:ISTA:57</a>","ama":"Kainmueller D, Jug F, Rother C, Meyers G. Graph matching problems for annotating C. Elegans. 2017. doi:<a href=\"https://doi.org/10.15479/AT:ISTA:57\">10.15479/AT:ISTA:57</a>","chicago":"Kainmueller, Dagmar, Florian Jug, Carsten Rother, and Gene Meyers. “Graph Matching Problems for Annotating C. Elegans.” Institute of Science and Technology Austria, 2017. <a href=\"https://doi.org/10.15479/AT:ISTA:57\">https://doi.org/10.15479/AT:ISTA:57</a>.","ieee":"D. Kainmueller, F. Jug, C. Rother, and G. Meyers, “Graph matching problems for annotating C. Elegans.” Institute of Science and Technology Austria, 2017.","mla":"Kainmueller, Dagmar, et al. <i>Graph Matching Problems for Annotating C. Elegans</i>. Institute of Science and Technology Austria, 2017, doi:<a href=\"https://doi.org/10.15479/AT:ISTA:57\">10.15479/AT:ISTA:57</a>.","short":"D. Kainmueller, F. Jug, C. Rother, G. Meyers, (2017).","ista":"Kainmueller D, Jug F, Rother C, Meyers G. 2017. Graph matching problems for annotating C. Elegans, Institute of Science and Technology Austria, <a href=\"https://doi.org/10.15479/AT:ISTA:57\">10.15479/AT:ISTA:57</a>."},"year":"2017","date_updated":"2024-02-21T13:46:31Z","tmp":{"legal_code_url":"https://creativecommons.org/publicdomain/zero/1.0/legalcode","short":"CC0 (1.0)","name":"Creative Commons Public Domain Dedication (CC0 1.0)","image":"/images/cc_0.png"},"ddc":["000"],"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_id":"5614","creator":"system","relation":"main_file","access_level":"open_access","date_updated":"2020-07-14T12:47:03Z","file_name":"IST-2017-57-v1+1_wormMatchingProblems.zip","content_type":"application/zip","date_created":"2018-12-12T13:02:54Z","file_size":327042819,"checksum":"3dc3e1306a66028a34181ebef2923139"}],"acknowledgement":"We thank Vladimir Kolmogorov and Stephan Saalfeld forinspiring discussions."},{"page":"31-60","quality_controlled":"1","publisher":"Springer Nature","article_type":"original","_id":"11680","scopus_import":"1","author":[{"last_name":"Alberts","first_name":"D.","full_name":"Alberts, D."},{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"}],"publication_status":"published","article_processing_charge":"No","date_created":"2022-07-28T06:50:51Z","title":"Average-case analysis of dynamic graph algorithms","intvolume":"        20","volume":20,"acknowledgement":"The authors would like to thank Emo Welzl for helpful discussions.","extern":"1","date_updated":"2023-02-21T16:33:27Z","year":"1998","citation":{"apa":"Alberts, D., &#38; Henzinger, M. H. (1998). Average-case analysis of dynamic graph algorithms. <i>Algorithmica</i>. Springer Nature. <a href=\"https://doi.org/10.1007/pl00009186\">https://doi.org/10.1007/pl00009186</a>","ama":"Alberts D, Henzinger MH. Average-case analysis of dynamic graph algorithms. <i>Algorithmica</i>. 1998;20:31-60. doi:<a href=\"https://doi.org/10.1007/pl00009186\">10.1007/pl00009186</a>","chicago":"Alberts, D., and Monika H Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” <i>Algorithmica</i>. Springer Nature, 1998. <a href=\"https://doi.org/10.1007/pl00009186\">https://doi.org/10.1007/pl00009186</a>.","ieee":"D. Alberts and M. H. Henzinger, “Average-case analysis of dynamic graph algorithms,” <i>Algorithmica</i>, vol. 20. Springer Nature, pp. 31–60, 1998.","short":"D. Alberts, M.H. Henzinger, Algorithmica 20 (1998) 31–60.","mla":"Alberts, D., and Monika H. Henzinger. “Average-Case Analysis of Dynamic Graph Algorithms.” <i>Algorithmica</i>, vol. 20, Springer Nature, 1998, pp. 31–60, doi:<a href=\"https://doi.org/10.1007/pl00009186\">10.1007/pl00009186</a>.","ista":"Alberts D, Henzinger MH. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 31–60."},"doi":"10.1007/pl00009186","day":"01","abstract":[{"text":"We present a model for edge updates with restricted randomness in dynamic graph algorithms and a general technique for analyzing the expected running time of an update operation. This model is able to capture the average case in many applications, since (1) it allows restrictions on the set of edges which can be used for insertions and (2) the type (insertion or deletion) of each update operation is arbitrary, i.e., not random. We use our technique to analyze existing and new dynamic algorithms for the following problems: maximum cardinality matching, minimum spanning forest, connectivity, 2-edge connectivity, k -edge connectivity, k -vertex connectivity, and bipartiteness. Given a random graph G with m 0 edges and n vertices and a sequence of l update operations such that the graph contains m i edges after operation i , the expected time for performing the updates for any l is O(llogn+∑li=1n/m−−√i) in the case of minimum spanning forests, connectivity, 2-edge connectivity, and bipartiteness. The expected time per update operation is O(n) in the case of maximum matching. We also give improved bounds for k -edge and k -vertex connectivity. Additionally we give an insertions-only algorithm for maximum cardinality matching with worst-case O(n) amortized time per insertion.","lang":"eng"}],"language":[{"iso":"eng"}],"keyword":["Dynamic graph algorithm","Average-case analysis","Minimum spanning forest","Connectivity","Bipartiteness","Maximum matching."],"publication":"Algorithmica","oa_version":"None","month":"01","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"11928"}]},"status":"public","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_published":"1998-01-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1432-0541"],"issn":["0178-4617"]}}]