@article{11675,
  abstract     = {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.},
  author       = {Bhattacharya, Sayan and Chakrabarty, Deeparnab and Henzinger, Monika H},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Dynamic algorithms, Data structures, Graph algorithms, Matching, Vertex cover},
  number       = {4},
  pages        = {1057--1080},
  publisher    = {Springer Nature},
  title        = {{Deterministic dynamic matching in O(1) update time}},
  doi          = {10.1007/s00453-019-00630-4},
  volume       = {82},
  year         = {2020},
}

@misc{5573,
  abstract     = {Graph matching problems for large displacement optical flow of RGB-D images.},
  author       = {Alhaija, Hassan and Sellent, Anita and Kondermann, Daniel and Rother, Carsten},
  keywords     = {graph matching, quadratic assignment problem<},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Graph matching problems for GraphFlow – 6D Large Displacement Scene Flow}},
  doi          = {10.15479/AT:ISTA:82},
  year         = {2018},
}

@misc{5561,
  abstract     = {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. },
  author       = {Kainmueller, Dagmar and Jug, Florian and Rother, Carsten and Meyers, Gene},
  keywords     = {graph matching, feature matching, QAP, MAP-inference},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Graph matching problems for annotating C. Elegans}},
  doi          = {10.15479/AT:ISTA:57},
  year         = {2017},
}

@article{11680,
  abstract     = {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.},
  author       = {Alberts, D. and Henzinger, Monika H},
  issn         = {1432-0541},
  journal      = {Algorithmica},
  keywords     = {Dynamic graph algorithm, Average-case analysis, Minimum spanning forest, Connectivity, Bipartiteness, Maximum matching.},
  pages        = {31--60},
  publisher    = {Springer Nature},
  title        = {{Average-case analysis of dynamic graph algorithms}},
  doi          = {10.1007/pl00009186},
  volume       = {20},
  year         = {1998},
}