Maximilian Probst Gutenberg

MaRDI QIDQ5020730zbMATH OpenFDO

List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

Publication	Date of Publication	Type
Practical expander decomposition	2026-05-26	Paper
Decremental APSP in unweighted digraphs versus an adaptive adversary	2026-05-12	Paper
Optimal electrical oblivious routing on expanders	2026-01-14	Paper
Maximum flow and minimum-cost flow in almost-linear time Journal of the ACM	2025-08-21	Paper
A deterministic almost-linear time algorithm for minimum-cost flow	2025-08-15	Paper
Maximum flow and minimum-cost flow in almost-linear time	2025-08-15	Paper
Deterministic decremental SSSP and approximate min-cost flow in almost-linear time	2025-08-13	Paper
Deterministic decremental reachability, SCC, and shortest paths via directed expanders and congestion balancing	2025-08-12	Paper
Near-optimal decremental SSSP in dense weighted digraphs	2025-08-12	Paper
Incremental approximate maximum flow on undirected graphs in subpolynomial update time	2024-11-28	Paper
Incremental SSSP for sparse digraphs beyond the hopset barrier	2024-07-19	Paper
A near-optimal offline algorithm for dynamic all-pairs shortest paths in planar digraphs	2024-07-19	Paper
Hardness results for Laplacians of simplicial complexes via sparse-linear equation complete gadgets	2024-06-24	Paper
Maintaining expander decompositions via sparse cuts	2024-05-14	Paper
A simple algorithm for multiple-source shortest paths in planar digraphs	2024-05-14	Paper
A simple framework for finding balanced sparse cuts via APSP	2024-05-14	Paper
Deterministic incremental APSP with polylogarithmic update time and stretch	2024-05-08	Paper
scientific article; zbMATH DE number 7788448 (Why is no real title available?) (available as arXiv preprint)	2024-01-15	Paper
Decremental strongly connected components and single-source reachability in near-linear time SIAM Journal on Computing	2022-01-07	Paper
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
Decremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
Fully-Dynamic All-Pairs Shortest Paths: Improved Worst-Case Time and Space Bounds Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms	2021-02-02	Paper
New algorithms and hardness for incremental single-source shortest paths in directed graphs Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing	2021-01-19	Paper

Research outcomes over time

This page was built for person: Maximilian Probst Gutenberg