---
res:
  bibo_abstract:
  - "We study the problem of computing a minimum cut in a simple, undirected graph
    and give a deterministic O(m log2 n log log2 n) time algorithm. This improves
    both on the best previously known deterministic running time of O(m log12 n) (Kawarabayashi
    and Thorup [12]) and the best previously known randomized running time of O(mlog3n)
    (Karger [11]) for this problem, though Karger's algorithm can be further applied
    to weighted graphs.\r\n\r\nOur approach is using the Kawarabayashi and Tho- rup
    graph compression technique, which repeatedly finds low-conductance cuts. To find
    these cuts they use a diffusion-based local algorithm. We use instead a flow-
    based local algorithm and suitably adjust their framework to work with our flow-based
    subroutine. Both flow and diffusion based methods have a long history of being
    applied to finding low conductance cuts. Diffusion algorithms have several variants
    that are naturally local while it is more complicated to make flow methods local.
    Some prior work has proven nice properties for local flow based algorithms with
    respect to improving or cleaning up low conductance cuts. Our flow subroutine,
    however, is the first that is both local and produces low conductance cuts. Thus,
    it may be of independent interest.@eng"
  bibo_authorlist:
  - 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
  - foaf_Person:
      foaf_givenName: Satish
      foaf_name: Rao, Satish
      foaf_surname: Rao
  - foaf_Person:
      foaf_givenName: Di
      foaf_name: Wang, Di
      foaf_surname: Wang
  bibo_doi: 10.1137/1.9781611974782.125
  dct_date: 2017^xs_gYear
  dct_language: eng
  dct_publisher: Society for Industrial and Applied Mathematics@
  dct_title: Local flow partitioning for faster edge connectivity@
...