Maximilian Probst Gutenberg

70 papers A* 30A 1Journal 37Unranked 2
YearRankTypeTitle / Venue / Authors
2026 A* conf
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows.
SODA
Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan, Wuwei Yuan
2026 A* conf
Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time.
SODA
Simon Meierhans, Maximilian Probst Gutenberg
2026 A* conf
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time.
SODA
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2025 J jnl
A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition.
CoRR
Maximilian Probst Gutenberg, Weixuan Yuan
2025 J jnl
A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows.
CoRR
Maximilian Probst Gutenberg, Rasmus Kyng, Weixuan Yuan, Wuwei Yuan
2025 A* conf
Deterministic Almost-Linear-Time Gomory-Hu Trees.
FOCS
Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Weixuan Yuan, Wuwei Yuan
2025 J jnl
Deterministic Almost-Linear-Time Gomory-Hu Trees.
CoRR
Amir Abboud, Rasmus Kyng, Jason Li, Debmalya Panigrahi, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Weixuan Yuan, Wuwei Yuan
2025 J jnl
Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time.
CoRR
Simon Meierhans, Maximilian Probst Gutenberg
2025 J jnl
Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time.
CoRR
Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2025 J jnl
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.
J. ACM
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
2025 A* conf
Near-Optimal Algorithm for Directed Expander Decompositions.
ICALP
Aurelio L. Sulser, Maximilian Probst Gutenberg
2025 A* conf
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal.
SODA
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2025 J jnl
Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings.
CoRR
Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder
2025 A* conf
Random-Shift Revisited: Tight Approximations for Tree Embeddings and ℓ₁-Oblivious Routings.
FOCS
Rasmus Kyng, Maximilian Probst Gutenberg, Tim Rieder
2025 J jnl
Reviving Thorup's Shortcut Conjecture.
CoRR
Aaron Bernstein, Henry L. Fleischmann, Maximilian Probst Gutenberg, Bernhard Haeupler, Gary Hoppenworth, Yonggang Jiang, George Z. Li, Seth Pettie, Thatchaphol Saranurak, Leon Schiller
2024 A* conf
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications.
STOC
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
2024 J jnl
A Simple and Near-Optimal Algorithm for Directed Expander Decompositions.
CoRR
Aurelio L. Sulser, Maximilian Probst Gutenberg
2024 A* conf
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality.
FOCS
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva
2024 J jnl
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality.
CoRR
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva
2024 A* conf
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow.
STOC
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg
2024 A* conf
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.
SODA
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2024 A* conf
Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs.
FOCS
Arnold Filtser, Gramoz Goranci, Neel Patel, Maximilian Probst Gutenberg
2024 A* conf
Optimal Electrical Oblivious Routing on Expanders.
ICALP
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
2024 J jnl
Optimal Electrical Oblivious Routing on Expanders.
CoRR
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
2024 J jnl
Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal.
CoRR
Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2024 A conf
Practical Expander Decomposition.
ESA
Lars Gottesbüren, Nikos Parotsidis, Maximilian Probst Gutenberg
2023 A* conf
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.
FOCS
Jan van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2023 J jnl
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow.
CoRR
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2023 J jnl
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications.
CoRR
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
2023 — conf
A Simple Framework for Finding Balanced Sparse Cuts via APSP.
SOSA
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
2023 J jnl
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow.
CoRR
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg
2023 J jnl
Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow.
Commun. ACM
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
2023 A* conf
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch.
STOC
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
2023 J jnl
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time.
CoRR
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
2023 A* conf
Maintaining Expander Decompositions via Sparse Cuts.
SODA
Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu
2022 A* conf
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs.
SODA
Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2022 — conf
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs.
SOSA
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2022 J jnl
A Simple Framework for Finding Balanced Sparse Cuts via APSP.
CoRR
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
2022 J jnl
Derandomizing Directed Random Walks in Almost-Linear Time.
CoRR
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
2022 J jnl
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch.
CoRR
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
2022 A* conf
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
ICALP
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2022 A* conf
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets.
ICALP
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang
2022 J jnl
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets.
CoRR
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang
2022 A* conf
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier.
SODA
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
2022 J jnl
Maintaining Expander Decompositions via Sparse Cuts.
CoRR
Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu
2022 A* conf
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.
FOCS
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
2022 J jnl
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.
CoRR
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
2021 J jnl
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs.
CoRR
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2021 A* conf
Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary.
ICALP
Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2021 A* conf
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.
FOCS
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2021 J jnl
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.
CoRR
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2021 J jnl
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier.
CoRR
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
2021 A* conf
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners.
SODA
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
2020 J jnl
Decremental APSP in Directed Graphs Versus an Adaptive Adversary.
CoRR
Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 A* conf
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary.
SODA
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 J jnl
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary.
CoRR
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 A* conf
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler.
SODA
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 J jnl
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler.
CoRR
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 A* conf
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.
FOCS
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2020 J jnl
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.
CoRR
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
2020 A* conf
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds.
SODA
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 J jnl
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds.
CoRR
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 J jnl
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.
CoRR
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
2020 J jnl
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs.
CoRR
Maximilian Probst Gutenberg
2020 A* conf
Near-Optimal Decremental SSSP in Dense Weighted Digraphs.
FOCS
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 J jnl
Near-Optimal Decremental SSSP in Dense Weighted Digraphs.
CoRR
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
2020 J jnl
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs.
CoRR
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
2020 J jnl
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners.
CoRR
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
2020 A* conf
New algorithms and hardness for incremental single-source shortest paths in directed graphs.
STOC
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
2019 J jnl
Decremental Strongly Connected Components and Single-Source Reachability in Near-Linear Time.
SIAM J. Comput.
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen