Near-optimal algorithm for directed expander decompositions
From MaRDI portal
Cites work
- A deterministic almost-linear time algorithm for minimum-cost flow
- A faster combinatorial algorithm for maximum bipartite matching
- A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
- A new approach to the maximum-flow problem
- A simple deterministic algorithm for edge connectivity
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Decremental all-pairs shortest paths in deterministic near-linear time
- Derandomizing directed random walks in almost-linear time
- Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing
- Deterministic decremental SSSP and approximate min-cost flow in almost-linear time
- Deterministic mincut in almost-linear time
- Dynamic minimum spanning forest with subpolynomial worst-case update time
- Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
- Expander decomposition and pruning: faster, stronger, and simpler
- Fully dynamic s-t edge connectivity in subpolynomial time (extended abstract)
- Fully dynamic min-cut of superconstant size in subpolynomial time
- Fully-dynamic graph sparsifiers against an adaptive adversary
- Fully-dynamic minimum spanning forest with improved worst-case update time
- Graph partitioning using single commodity flows
- scientific article; zbMATH DE number 7788412 (Why is no real title available?)
- scientific article; zbMATH DE number 7788470 (Why is no real title available?)
- scientific article; zbMATH DE number 7788485 (Why is no real title available?)
- Local flow partitioning for faster edge connectivity
- Maintaining expander decompositions via sparse cuts
- Maximum flow and minimum-cost flow in almost-linear time
- 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
- Near-optimal decremental SSSP in dense weighted digraphs
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- The Pseudoflow Algorithm: A New Algorithm for the Maximum-Flow Problem
This page was built for publication: Near-optimal algorithm for directed expander decompositions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7397590)
