Deterministic Edge Connectivity in Near-Linear Time

DOI10.1145/3274663zbMath1426.68217arXiv1411.5123OpenAlexW2963972775WikidataQ128753538 ScholiaQ128753538MaRDI QIDQ4625670

Mikkel Thorup, Ken-ichi Kawarabayashi

Publication date: 25 February 2019

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.5123

zbMATH Keywords

minimum cutedge connectivitysimple graphsdeterministic near-linear time

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Connectivity (05C40)

Related Items (6)

Minimum Cuts in Surface Graphs ⋮ Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Generalized cut trees for edge-connectivity ⋮ Finding densest \(k\)-connected subgraphs ⋮ Compact cactus representations of all non-trivial min-cuts ⋮ Local Flow Partitioning for Faster Edge Connectivity

This page was built for publication: Deterministic Edge Connectivity in Near-Linear Time