skip to main content
Idioma:

Deterministic Edge Connectivity in Near-Linear Time

Kawarabayashi, Ken-Ichi ; Thorup, Mikkel

Journal of the ACM, 2019-01, Vol.66 (1), p.1-50 [Periódico revisado por pares]

New York: Association for Computing Machinery

Texto completo disponível

Citações Citado por
  • Título:
    Deterministic Edge Connectivity in Near-Linear Time
  • Autor: Kawarabayashi, Ken-Ichi ; Thorup, Mikkel
  • Assuntos: Algorithms ; Apexes ; Computer engineering ; Computer simulation ; Connectivity ; Graph theory ; Monte Carlo simulation ; Optimization algorithms ; Randomization ; Resistance ; Search engines ; Vertex sets
  • É parte de: Journal of the ACM, 2019-01, Vol.66 (1), p.1-50
  • Descrição: We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is for a simple undirected unweighted graph G with n vertices and m edges. This is the first o ( mn ) time deterministic algorithm for the problem. Our algorithm is easily extended to find a concrete minimum edge-cut. In fact, we can construct the classic cactus representation of all minimum cuts in near-linear time. The previous fastest deterministic algorithm by Gabow from STOC '91 took Õ( m +λ 2 n ), where λ is the edge connectivity, but λ can be as big as n −1. Karger presented a randomized near-linear time Monte Carlo algorithm for the minimum cut problem at STOC’96, but the returned cut is only minimum with high probability. Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph G with minimum degree Δ, producing a multigraph Ḡ with Õ( m /Δ) edges, which preserves all minimum cuts of G with at least two vertices on each side. In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS’06. Normally, such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed.
  • Editor: New York: Association for Computing Machinery
  • Idioma: Inglês
Voltar para lista de resultados

  • Realização: ABCD-USP USP   Logos de Redes Sociais: Freepik

Buscando em bases de dados remotas. Favor aguardar.