Vertex connectivity in poly-logarithmic max-flows

DOI10.1145/3743670MaRDI QIDQ6912093zbMATH OpenFDO

Authors Jason Li, Danupon Nanongkai, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai

Publication date 23 October 2025

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1145/3743670

zbMATH Keywords

algorithmic graph theoryvertex connectivity

Mathematics Subject Classification ID

Flows in graphs (05C21) Connectivity (05C40) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• A deterministic almost-linear time algorithm for minimum-cost flow
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph
• A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
• A new approach to the maximum-flow problem
• A probabilistic algorithm for vertex connectivity of graphs
• A refined laser method and faster matrix multiplication
• An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
• Breaking quadratic time for small vertex connectivity and an approximation scheme
• Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
• Computing Vertex Connectivity: New Bounds from Old Techniques
• Depth-First Search and Linear Graph Algorithms
• Deterministic min-cut in poly-logarithmic max-flows
• Deterministic small vertex connectivity in almost linear time
• Distributed connectivity decomposition
• Dividing a Graph into Triconnected Components
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• Improved algorithms for graph four-connectivity
• Local flow partitioning for faster edge connectivity
• Maximum flow and minimum-cost flow in almost-linear time
• Network Flow and Testing Graph Connectivity
• New bounds for matrix multiplication: from alpha to omega
• Rubber bands, convex embeddings and graph connectivity
• Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
• The space complexity of approximating the frequency moments
• Using expander graphs to find vertex connectivity

This page was built for publication: Vertex connectivity in poly-logarithmic max-flows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6912093)