Maximilian Probst Gutenberg

Publication Activity (10 Years)

Years Active: 2020-2024
Publications (10 Years): 51

Top Topics

Connected Components

Top Venues

Publications

Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
Optimal Electrical Oblivious Routing on Expanders. ICALP (2024)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg, Sushant Sachdeva
Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality. CoRR (2024)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. SODA (2024)
Cella Florescu, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
Optimal Electrical Oblivious Routing on Expanders. CoRR (2024)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and Their Applications. STOC (2024)
Aurelio L. Sulser, Maximilian Probst Gutenberg
A Simple and Near-Optimal Algorithm for Directed Expander Decompositions. CoRR (2024)
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. STOC (2024)
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch. STOC (2023)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
A Dynamic Shortest Paths Toolbox: Low-Congestion Vertex Sparsifiers and their Applications. CoRR (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time. CoRR (2023)
Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu
Maintaining Expander Decompositions via Sparse Cuts. SODA (2023)
Jan Van den Brand, Li Chen, Richard Peng, Rasmus Kyng, Yang P. Liu, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. FOCS (2023)
Jan van den Brand, Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva, Aaron Sidford
A Deterministic Almost-Linear Time Algorithm for Minimum-Cost Flow. CoRR (2023)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Almost-Linear-Time Algorithms for Maximum Flow and Minimum-Cost Flow. Commun. ACM 66 (12) (2023)
Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow. CoRR (2023)
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
A Simple Framework for Finding Balanced Sparse Cuts via APSP. SOSA (2023)
Debarati Das, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs. SODA (2022)
Yiding Hua, Rasmus Kyng, Maximilian Probst Gutenberg, Zihang Wu
Maintaining Expander Decompositions via Sparse Cuts. CoRR (2022)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. FOCS (2022)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. FOCS (2022)
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. SOSA (2022)
Li Chen, Rasmus Kyng, Maximilian Probst Gutenberg, Sushant Sachdeva
A Simple Framework for Finding Balanced Sparse Cuts via APSP. CoRR (2022)
Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, Sushant Sachdeva
Maximum Flow and Minimum-Cost Flow in Almost-Linear Time. CoRR (2022)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. ICALP (2022)
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch. CoRR (2022)
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. CoRR (2022)
Ming Ding, Rasmus Kyng, Maximilian Probst Gutenberg, Peng Zhang
Hardness Results for Laplacians of Simplicial Complexes via Sparse-Linear Equation Complete Gadgets. ICALP (2022)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Derandomizing Directed Random Walks in Almost-Linear Time. CoRR (2022)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier. SODA (2022)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. FOCS (2021)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time. CoRR (2021)
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. SODA (2021)
Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Decremental APSP in Unweighted Digraphs Versus an Adaptive Adversary. ICALP (2021)
Rasmus Kyng, Simon Meierhans, Maximilian Probst Gutenberg
Incremental SSSP for Sparse Digraphs Beyond the Hopset Barrier. CoRR (2021)
Debarati Das, Evangelos Kipouridis, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
A Simple Algorithm for Multiple-Source Shortest Paths in Planar Digraphs. CoRR (2021)
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. CoRR (2020)
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs. CoRR (2020)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. FOCS (2020)
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds. SODA (2020)
Jacob Evald, Viktor Fredslund-Hansen, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Decremental APSP in Directed Graphs Versus an Adaptive Adversary. CoRR (2020)
Aaron Bernstein, Maximilian Probst Gutenberg, Thatchaphol Saranurak
Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing. CoRR (2020)
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds. CoRR (2020)
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Near-Optimal Decremental SSSP in Dense Weighted Digraphs. CoRR (2020)
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary. SODA (2020)
Maximilian Probst Gutenberg
Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs. CoRR (2020)
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler. SODA (2020)
Aaron Bernstein, Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Near-Optimal Decremental SSSP in Dense Weighted Digraphs. FOCS (2020)
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, He Sun
Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary. CoRR (2020)
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler. CoRR (2020)
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
New algorithms and hardness for incremental single-source shortest paths in directed graphs. STOC (2020)
Maximilian Probst Gutenberg, Christian Wulff-Nilsen
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary. CoRR (2020)