Maximum-flow and minimum-cut sensitivity oracles for directed graphs
From MaRDI portal
Cites work
- \(f\)-sensitivity distance oracles and routing schemes
- A deterministic almost-linear time algorithm for minimum-cost flow
- A fast algorithm for finding dominators in a flowgraph
- A new approach to computing maximum flows using electrical flows
- A new approach to the maximum-flow problem
- Almost-linear time algorithms for decremental graphs: min-cost flow and more via duality
- An efficient algorithm for all-pairs bounded edge connectivity
- An efficient strongly connected components algorithm in the fault tolerant model
- An optimal dual fault tolerant reachability oracle
- Beyond the flow decomposition barrier
- Connectivity oracles for failure prone graphs
- Connectivity oracles for graphs subject to vertex failures
- Dinitz' algorithm: the original version and Even's version
- Directed flow-augmentation
- Dual-failure distance and connectivity oracles
- Faster algorithms for all-pairs bounded min-cuts
- Faster maxflow via improved dynamic spectral vertex sparsifiers
- Fault tolerant subgraph for single source reachability: generic and optimal
- Fault-tolerant spanners
- Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract)
- Fully dynamic electrical flows: sparse maxflow faster than Goldberg-Rao
- Fully dynamic exact edge connectivity in sublinear time
- Fully dynamic min-cut of superconstant size in subpolynomial time
- Fully-dynamic min-cut
- scientific article; zbMATH DE number 5764802 (Why is no real title available?)
- scientific article; zbMATH DE number 910886 (Why is no real title available?)
- Incremental approximate maximum flow on undirected graphs in subpolynomial update time
- Maintaining exact distances under multiple edge failures
- Maximum flow by augmenting paths in \(n^{2+o(1)}\) time
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
- Minimum\(+1\) \((s,t)\)-cuts and dual edge sensitivity oracle
- Multiple source dual fault tolerant BFS trees
- New extremal bounds for reachability and strong-connectivity preservers under failures
- New results on fault tolerant geometric spanners
- Optimal sensitivity oracle for Steiner mincut
- Oracles for Distances Avoiding a Failed Node or Link
- Preserving distances in very faulty graphs
- Replacement paths and distance sensitivity oracles via fast matrix multiplication
- Sensitive distance and reachability oracles for large batch updates
- Sensitivity and dynamic distance oracles via generic matrices and Frobenius form
- Sensitivity oracles for all-pairs mincuts
- Sparse fault-tolerant BFS trees
- Strong connectivity in directed graphs under failures, with applications
- Strong connectivity in directed graphs under failures, with applications
- The connectivity carcass of a vertex subset in a graph and its incremental maintenance
- The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd Case
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Unit capacity maxflow in almost \(O(m^{4/3})\) time
- Vertex fault tolerant additive spanners
- Vital edges for (s,t)-mincut: efficient algorithms, compact structures, \& optimal sensitivity oracles
This page was built for publication: Maximum-flow and minimum-cut sensitivity oracles for directed graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7445509)