---
_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: '11679'
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."
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: V.
  full_name: King, V.
  last_name: King
- first_name: T.
  full_name: Warnow, T.
  last_name: Warnow
citation:
  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>
  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>
  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>.
  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.
  ista: Henzinger MH, King V, Warnow T. 1999. Constructing a tree from homeomorphic
    subtrees, with applications to computational evolutionary biology. Algorithmica.
    24, 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>.
  short: M.H. Henzinger, V. King, T. Warnow, Algorithmica 24 (1999) 1–13.
date_created: 2022-07-27T15:02:28Z
date_published: 1999-05-01T00:00:00Z
date_updated: 2023-02-21T16:33:24Z
day: '01'
doi: 10.1007/pl00009268
extern: '1'
intvolume: '        24'
keyword:
- Algorithms
- Data structures
- Evolutionary biology
- Theory of databases
language:
- iso: eng
month: '05'
oa_version: None
page: 1-13
publication: Algorithmica
publication_identifier:
  eissn:
  - 1432-0541
  issn:
  - 0178-4617
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '11927'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Constructing a tree from homeomorphic subtrees, with applications to computational
  evolutionary biology
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '1999'
...