[{"date_created":"2022-07-27T14:31:06Z","keyword":["Dynamic algorithms","Data structures","Graph algorithms","Matching","Vertex cover"],"intvolume":"        82","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","article_processing_charge":"No","quality_controlled":"1","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"month":"04","article_type":"original","volume":82,"publisher":"Springer Nature","year":"2020","language":[{"iso":"eng"}],"doi":"10.1007/s00453-019-00630-4","type":"journal_article","oa":1,"_id":"11675","author":[{"full_name":"Bhattacharya, Sayan","first_name":"Sayan","last_name":"Bhattacharya"},{"last_name":"Chakrabarty","full_name":"Chakrabarty, Deeparnab","first_name":"Deeparnab"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530"}],"date_published":"2020-04-01T00:00:00Z","citation":{"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.","short":"S. Bhattacharya, D. Chakrabarty, M.H. Henzinger, Algorithmica 82 (2020) 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>","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>"},"issue":"4","scopus_import":"1","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00453-019-00630-4"}],"title":"Deterministic dynamic matching in O(1) update time","publication":"Algorithmica","date_updated":"2022-09-12T08:55:46Z","status":"public","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."}],"oa_version":"Published Version","page":"1057-1080","publication_status":"published","day":"01"},{"status":"public","license":"https://creativecommons.org/publicdomain/zero/1.0/","type":"research_data","doi":"10.15479/AT:ISTA:82","date_updated":"2024-02-21T13:41:17Z","publisher":"Institute of Science and Technology Austria","year":"2018","date_published":"2018-01-04T00:00:00Z","oa_version":"Published Version","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"},"day":"04","abstract":[{"lang":"eng","text":"Graph matching problems for large displacement optical flow of RGB-D images."}],"author":[{"full_name":"Alhaija, Hassan","first_name":"Hassan","last_name":"Alhaija"},{"last_name":"Sellent","first_name":"Anita","full_name":"Sellent, Anita"},{"first_name":"Daniel","full_name":"Kondermann, Daniel","last_name":"Kondermann"},{"last_name":"Rother","full_name":"Rother, Carsten","first_name":"Carsten"}],"oa":1,"contributor":[{"last_name":"Swoboda","id":"446560C6-F248-11E8-B48F-1D18A9856A87","contributor_type":"researcher","first_name":"Paul"}],"_id":"5573","ddc":["001"],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file_date_updated":"2020-07-14T12:47:05Z","keyword":["graph matching","quadratic assignment problem<"],"has_accepted_license":"1","date_created":"2018-12-12T12:31:36Z","citation":{"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>.","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>","short":"H. Alhaija, A. Sellent, D. Kondermann, C. Rother, (2018).","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>.","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>","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."},"department":[{"_id":"VlKo"}],"datarep_id":"82","related_material":{"link":[{"url":"https://doi.org/10.1007/978-3-319-24947-6_23","relation":"research_paper"}]},"title":"Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow","file":[{"date_updated":"2020-07-14T12:47:05Z","date_created":"2018-12-12T13:02:34Z","checksum":"53c17082848e12f3c2e1b4185b578208","file_id":"5600","file_size":1737958,"file_name":"IST-2018-82-v1+1_GraphFlowMatchingProblems.zip","content_type":"application/zip","relation":"main_file","access_level":"open_access","creator":"system"}],"month":"01"},{"has_accepted_license":"1","keyword":["graph matching","feature matching","QAP","MAP-inference"],"file_date_updated":"2020-07-14T12:47:03Z","ddc":["000"],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","acknowledgement":"We thank Vladimir Kolmogorov and Stephan Saalfeld forinspiring discussions.","citation":{"ieee":"D. Kainmueller, F. Jug, C. Rother, and G. Meyers, “Graph matching problems for annotating C. Elegans.” Institute of Science and Technology Austria, 2017.","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>.","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>","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>.","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>","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)."},"department":[{"_id":"VlKo"}],"date_created":"2018-12-12T12:31:32Z","file":[{"date_created":"2018-12-12T13:02:54Z","file_id":"5614","checksum":"3dc3e1306a66028a34181ebef2923139","date_updated":"2020-07-14T12:47:03Z","file_name":"IST-2017-57-v1+1_wormMatchingProblems.zip","file_size":327042819,"access_level":"open_access","content_type":"application/zip","relation":"main_file","creator":"system"}],"title":"Graph matching problems for annotating C. Elegans","datarep_id":"57","month":"02","type":"research_data","status":"public","year":"2017","date_updated":"2024-02-21T13:46:31Z","publisher":"Institute of Science and Technology Austria","doi":"10.15479/AT:ISTA:57","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. "}],"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"},"day":"13","oa_version":"Published Version","date_published":"2017-02-13T00:00:00Z","_id":"5561","oa":1,"author":[{"full_name":"Kainmueller, Dagmar","first_name":"Dagmar","last_name":"Kainmueller"},{"last_name":"Jug","first_name":"Florian","full_name":"Jug, Florian"},{"first_name":"Carsten","full_name":"Rother, Carsten","last_name":"Rother"},{"last_name":"Meyers","first_name":"Gene","full_name":"Meyers, Gene"}]},{"volume":20,"article_type":"original","month":"01","publication_identifier":{"issn":["0178-4617"],"eissn":["1432-0541"]},"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","article_processing_charge":"No","intvolume":"        20","keyword":["Dynamic graph algorithm","Average-case analysis","Minimum spanning forest","Connectivity","Bipartiteness","Maximum matching."],"date_created":"2022-07-28T06:50:51Z","acknowledgement":"The authors would like to thank Emo Welzl for helpful discussions.","date_published":"1998-01-01T00:00:00Z","author":[{"first_name":"D.","full_name":"Alberts, D.","last_name":"Alberts"},{"full_name":"Henzinger, Monika H","first_name":"Monika H","orcid":"0000-0002-5008-6530","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger"}],"_id":"11680","type":"journal_article","doi":"10.1007/pl00009186","language":[{"iso":"eng"}],"year":"1998","publisher":"Springer Nature","publication":"Algorithmica","title":"Average-case analysis of dynamic graph algorithms","related_material":{"record":[{"id":"11928","status":"public","relation":"earlier_version"}]},"scopus_import":"1","citation":{"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>","ista":"Alberts D, Henzinger MH. 1998. Average-case analysis of dynamic graph algorithms. Algorithmica. 20, 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>.","short":"D. Alberts, M.H. Henzinger, Algorithmica 20 (1998) 31–60.","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>","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.","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>."},"day":"01","publication_status":"published","page":"31-60","oa_version":"None","abstract":[{"lang":"eng","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."}],"status":"public","date_updated":"2023-02-21T16:33:27Z"}]