---
res:
  bibo_abstract:
  - "In 1996, Karger [Kar96] gave a startling randomized algorithm that finds a minimum-cut
    in a (weighted) graph in time O(m log3 n) which he termed near-linear time meaning
    linear (in the size of the input) times a polylogarthmic factor. In this paper,
    we give the first deterministic algorithm which runs in near-linear time for weighted
    graphs.\r\nPreviously, the breakthrough results of Kawarabayashi and Thorup [KT19]
    gave a near-linear time algorithm for simple graphs (which was improved to have
    running time O(m log2 n log log n) in [HRW20].) The main technique here is a clustering
    procedure that perfectly preserves minimum cuts. Recently, Li [Li21] gave an m1+o(1)
    deterministic minimum-cut algorithm for weighted graphs; this form of running
    time has been termed “almost-linear”. Li uses almost-linear time deterministic
    expander decompositions which do not perfectly preserve minimum cuts, but he can
    use these clusterings to, in a sense, “derandomize” the methods of Karger.\r\nIn
    terms of techniques, we provide a structural theorem that says there exists a
    sparse clustering that preserves minimum cuts in a weighted graph with o(1) error.
    In addition, we construct it deterministically in near linear time. This was done
    exactly for simple graphs in [KT19, HRW20] and with polylogarithmic error for
    weighted graphs in [Li21]. Extending the techniques in [KT19, HRW20] to weighted
    graphs presents significant challenges, and moreover, the algorithm can only polylogarithmically
    approximately preserve minimum cuts. A remaining challenge is to reduce the polylogarithmic-approximate
    clusterings to 1 + o(1/ log n)-approximate so that they can be applied recursively
    as in [Li21] over O(log n) many levels. This is an additional challenge that requires
    building on properties of tree-packings in the presence of a wide range of edge
    weights to, for example, find sources for local flow computations which identify
    minimum cuts that cross clusters.@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: Jason
      foaf_name: Li, Jason
      foaf_surname: Li
  - 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.9781611977912.111
  dct_date: 2024^xs_gYear
  dct_language: eng
  dct_publisher: Society for Industrial and Applied Mathematics@
  dct_title: Deterministic near-linear time minimum cut in weighted graphs@
...