Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Brand, Jan van den, Chen, Li, Kyng, Rasmus, Liu, Yang P., Meierhans, Simon, Gutenberg, Maximilian Probst, Sachdeva, Sushant
Formato:	Preprint
Publicado:	2024
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Optimal Electrical Oblivious Routing on Expanders
por: Florescu, Cella, et al.
Publicado: (2024)

An Approximation Algorithm for Graph Label Selection
por: John, Josia, et al.
Publicado: (2026)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
por: Meierhans, Simon, et al.
Publicado: (2025)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
por: Kyng, Rasmus, et al.
Publicado: (2025)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
por: Meierhans, Simon, et al.
Publicado: (2025)

Deterministic Almost-Linear-Time Gomory-Hu Trees
por: Abboud, Amir, et al.
Publicado: (2025)

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
por: Gutenberg, Maximilian Probst, et al.
Publicado: (2025)

A Simple Dynamic Spanner via APSP
por: Kyng, Rasmus, et al.
Publicado: (2024)

Bootstrapping Dynamic APSP via Sparsification
por: Kyng, Rasmus, et al.
Publicado: (2024)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
por: Chen, Daoyuan, et al.
Publicado: (2024)

Near-Optimal Algorithm for Directed Expander Decompositions
por: Sulser, Aurelio L., et al.
Publicado: (2024)

Iterative Refinement for $\ell_p$-norm Regression
por: Adil, Deeksha, et al.
Publicado: (2019)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
por: Gutenberg, Maximilian Probst, et al.
Publicado: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
por: Das, Debarati, et al.
Publicado: (2026)

Acceleration for Distributed Transshipment and Parallel Maximum Flow
por: Grunau, Christoph, et al.
Publicado: (2025)

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
por: Brand, Jan van den, et al.
Publicado: (2025)

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
por: Ashvinkumar, Vikrant, et al.
Publicado: (2026)

Partial Implementation of Max Flow and Min Cost Flow in Almost-Linear Time
por: Kavi, Nithin
Publicado: (2024)

Computing Flows in Subquadratic Space
por: Brand, Jan van den, et al.
Publicado: (2026)

Acceleration Meets Inverse Maintenance: Faster $\ell_{\infty}$-Regression
por: Adil, Deeksha, et al.
Publicado: (2024)

Faster Min-Cost Flow and Approximate Tree Decomposition on Bounded Treewidth Graphs
por: Dong, Sally, et al.
Publicado: (2023)

Eulerian Graph Sparsification by Effective Resistance Decomposition
por: Jambulapati, Arun, et al.
Publicado: (2024)

A Tight Bound on Localization of Electrical Flows
por: Gurel-Gurevich, Ori, et al.
Publicado: (2026)

Faster Graph Embeddings via Coarsening
por: Fahrbach, Matthew, et al.
Publicado: (2020)

Dynamic Rank, Basis, and Matching
por: Brand, Jan van den, et al.
Publicado: (2026)

Bellman-Ford in Almost-Linear Time for Dense Graphs
por: Li, George Z., et al.
Publicado: (2026)

Universally Optimal Decremental Tree Minima
por: Berendsohn, Benjamin Aram
Publicado: (2026)

Entropy Regularization and Faster Decremental Matching in General Graphs
por: Chen, Jiale, et al.
Publicado: (2023)

An Optimal Algorithm for Stochastic Vertex Cover
por: Brand, Jan van den, et al.
Publicado: (2026)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
por: Dory, Michal, et al.
Publicado: (2022)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
por: Long, Yaowei, et al.
Publicado: (2024)

Reviving Thorup's Shortcut Conjecture
por: Bernstein, Aaron, et al.
Publicado: (2025)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
por: Chaplick, Steven, et al.
Publicado: (2024)

Deterministic Mincut in Almost-Linear Time
por: Li, Jason
Publicado: (2021)

Network Unreliability in Almost-Linear Time
por: Cen, Ruoxu, et al.
Publicado: (2025)

iFlow: An Interactive Max-Flow/Min-Cut Algorithms Visualizer
por: Ye, Muyang, et al.
Publicado: (2024)

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
por: Adil, Deeksha, et al.
Publicado: (2024)

Approximating Directed Connectivity in Almost-Linear Time
por: Quanrud, Kent
Publicado: (2025)

Vizing's Theorem in Deterministic Almost-Linear Time
por: Assadi, Sepehr, et al.
Publicado: (2025)

Almost Linear Size Edit Distance Sketch
por: Koucký, Michal, et al.
Publicado: (2024)