Breaking quadratic time for small vertex connectivity and an approximation scheme

DOI10.1145/3313276.3316394zbMath1433.68304arXiv1904.04453OpenAlexW2964010100MaRDI QIDQ5212766

Sorrachai Yingchareonthawornchai, Danupon Nanongkai, Thatchaphol Saranurak

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsvertex connectivitylocal flow algorithms

Mathematics Subject Classification ID

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

Related Items (3)

Faster connectivity in low-rank hypergraphs via expander decomposition ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Finding densest \(k\)-connected subgraphs

This page was built for publication: Breaking quadratic time for small vertex connectivity and an approximation scheme