Buchumschlag

Faster All-Pairs Minimum Cut: Bypassing Exact Max-Flow

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kenneth-Mordoch, Yotam, Krauthgamer, Robert
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

All-Pairs Minimum Cut using $\tilde{O}(n^{7/4})$ Cut Queries
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Faster Pseudo-Deterministic Minimum Cut
von: Kenneth-Mordoch, Yotam
Veröffentlicht: (2026)

Cut-Query Algorithms with Few Rounds
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Simple Algorithms for Fully Dynamic Edge Connectivity
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Cut Sparsification and Succinct Representation of Submodular Hypergraphs
von: Kenneth, Yotam, et al.
Veröffentlicht: (2023)

On the Adversarial Robustness of Online Importance Sampling
von: Kenneth-Mordoch, Yotam, et al.
Veröffentlicht: (2025)

Sketching Cuts in Graphs and Hypergraphs
von: Kogan, Dmitry, et al.
Veröffentlicht: (2014)

Faster Global Minimum Cut with Predictions
von: Moseley, Benjamin, et al.
Veröffentlicht: (2025)

Faster All-Pairs Optimal Electric Car Routing
von: Dorfman, Dani, et al.
Veröffentlicht: (2025)

(Almost) Ruling Out SETH Lower Bounds for All-Pairs Max-Flow
von: Trabelsi, Ohad
Veröffentlicht: (2023)

Faster Weak Expander Decompositions and Approximate Max Flow
von: Fleischmann, Henry, et al.
Veröffentlicht: (2025)

Stable coresets: Unleashing the power of uniform sampling
von: Carmel, Amir, et al.
Veröffentlicht: (2025)

Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
von: El-Hayek, Antoine, et al.
Veröffentlicht: (2025)

Minimum $s$--$t$ Cuts with Fewer Cut Queries
von: Jiang, Yonggang, et al.
Veröffentlicht: (2025)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
von: Ahi, Mridul, et al.
Veröffentlicht: (2025)

Deterministic Edge Connectivity and Max Flow using Subquadratic Cut Queries
von: Anand, Aditya, et al.
Veröffentlicht: (2024)

Faster Algorithms for Global Minimum Vertex-Cut in Directed Graphs
von: Chuzhoy, Julia, et al.
Veröffentlicht: (2025)

On Solving Linear Systems in Sublinear Time
von: Andoni, Alexandr, et al.
Veröffentlicht: (2018)

Thin Trees for Near Minimum Cuts
von: Klein, Nathan, et al.
Veröffentlicht: (2026)

Max-Cut with Multiple Cardinality Constraints
von: Makarychev, Yury, et al.
Veröffentlicht: (2025)

Streaming Max-Cut in General Metrics
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2025)

Local Max-Cut on Sparse Graphs
von: Schwartzman, Gregory
Veröffentlicht: (2023)

Near-Optimal Minimum Cuts in Hypergraphs at Scale
von: Chhabra, Adil, et al.
Veröffentlicht: (2025)

Max Cut with Small-Dimensional SDP Solutions
von: Chang, Hsien-Chih, et al.
Veröffentlicht: (2026)

Exact Optimization for Minimum Dominating Sets
von: Zhu, Enqiang, et al.
Veröffentlicht: (2025)

Moderate Dimension Reduction for $k$-Center Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2023)

Cactus Representation of Minimum Cuts: Derandomize and Speed up
von: He, Zhongtian, et al.
Veröffentlicht: (2024)

Streaming and Massively Parallel Algorithms for Euclidean Max-Cut
von: Menand, Nicolas, et al.
Veröffentlicht: (2025)

Space Complexity of Minimum Cut Problems in Single-Pass Streams
von: Ding, Matthew, et al.
Veröffentlicht: (2024)

Deterministic Near-Linear Time Minimum Cut in Weighted Graphs
von: Henzinger, Monika, et al.
Veröffentlicht: (2024)

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
von: de Vos, Tijn, et al.
Veröffentlicht: (2024)

Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
von: El-Hayek, Antoine, et al.
Veröffentlicht: (2024)

Coresets for Kernel Clustering
von: Jiang, Shaofeng H. -C., et al.
Veröffentlicht: (2021)

Near-Optimal Dimension Reduction for Facility Location
von: Huang, Lingxiao, et al.
Veröffentlicht: (2024)

Streaming Algorithms for Geometric Steiner Forest
von: Czumaj, Artur, et al.
Veröffentlicht: (2020)

iFlow: An Interactive Max-Flow/Min-Cut Algorithms Visualizer
von: Ye, Muyang, et al.
Veröffentlicht: (2024)

Minimum Stable Cut and Treewidth
von: Lampis, Michael
Veröffentlicht: (2021)

Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
von: Alman, Josh, et al.
Veröffentlicht: (2024)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
von: Kumar, Mithilesh, et al.
Veröffentlicht: (2024)

Minimum Cost Nowhere-zero Flows and Cut-balanced Orientations
von: Chandrasekaran, Karthekeyan, et al.
Veröffentlicht: (2025)