---
res:
  bibo_abstract:
  - The computation of the winning set for Büchi objectives in alternating games on
    graphs is a central problem in computer-aided verification with a large number
    of applications. The long-standing best known upper bound for solving the problem
    is Õ(n ⋅ m), where n is the number of vertices and m is the number of edges in
    the graph. We are the first to break the Õ(n ⋅ m) boundary by presenting a new
    technique that reduces the running time to O(n2). This bound also leads to O(n2)-time
    algorithms for computing the set of almost-sure winning vertices for Büchi objectives
    (1) in alternating games with probabilistic transitions (improving an earlier
    bound of Õ(n ⋅ m)), (2) in concurrent graph games with constant actions (improving
    an earlier bound of O(n3)), and (3) in Markov decision processes (improving for
    m>n4/3 an earlier bound of O(m ⋅ √m)). We then show how to maintain the winning
    set for Büchi objectives in alternating games under a sequence of edge insertions
    or a sequence of edge deletions in O(n) amortized time per operation. Our algorithms
    are the first dynamic algorithms for this problem. We then consider another core
    graph theoretic problem in verification of probabilistic systems, namely computing
    the maximal end-component decomposition of a graph. We present two improved static
    algorithms for the maximal end-component decomposition problem. Our first algorithm
    is an O(m ⋅ √m)-time algorithm, and our second algorithm is an O(n2)-time algorithm
    which is obtained using the same technique as for alternating Büchi games. Thus,
    we obtain an O(min &lcu;m ⋅ √m,n2})-time algorithm improving the long-standing
    O(n ⋅ m) time bound. Finally, we show how to maintain the maximal end-component
    decomposition of a graph under a sequence of edge insertions or a sequence of
    edge deletions in O(n) amortized time per edge deletion, and O(m) worst-case time
    per edge insertion. Again, our algorithms are the first dynamic algorithms for
    this problem.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  bibo_doi: 10.1145/2597631
  bibo_issue: '3'
  bibo_volume: 61
  dct_date: 2014^xs_gYear
  dct_identifier:
  - UT:000337201400001
  dct_language: eng
  dct_publisher: ACM@
  dct_title: Efficient and dynamic algorithms for alternating Büchi games and maximal
    end-component decomposition@
...