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