Aaron Bernstein

Greg Bodwin

Nicole Wein

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights.

[BibT_eX]

[DOI]

CoRR, 2023

Closing the Gap Between Directed Hopsets and Shortcut Sets.

[BibT_eX]

[DOI]

Nicole Wein

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method.

[BibT_eX]

[DOI]

Zachary Langley

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Dynamic Graph Algorithms (Dagstuhl Seminar 22461).

[BibT_eX]

[DOI]

Dagstuhl Reports, November, 2022

General bounds for incremental maximization.

[BibT_eX]

[DOI]

Math. Program., 2022

Negative-Weight Single-Source Shortest Paths in Almost-linear Time.

[BibT_eX]

[DOI]

CoRR, 2022

Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary.

[BibT_eX]

[DOI]

Jan van den Brand

Thatchaphol Saranurak

Aaron Sidford

He Sun

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Decremental Matching in General Graphs.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Negative-Weight Single-Source Shortest Paths in Near-linear Time.

[BibT_eX]

[DOI]

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching.

[BibT_eX]

[DOI]

Sebastian Forster

Monika Henzinger

ACM Trans. Algorithms, 2021

A framework for dynamic matching in weighted graphs.

[BibT_eX]

[DOI]

Zachary Langley

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Deterministic Decremental SSSP and Approximate Min-Cost Flow in Almost-Linear Time.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

Incremental SCC Maintenance in Sparse Graphs.

[BibT_eX]

[DOI]

Seth Pettie

Proceedings of the 29th Annual European Symposium on Algorithms, 2021

2020

Improved Bound for Matching in Random-Order Streams.

[BibT_eX]

[DOI]

CoRR, 2020

Improved Bounds for Distributed Load Balancing.

[BibT_eX]

[DOI]

Zachary Langley

Proceedings of the 34th International Symposium on Distributed Computing, 2020

Improved Bounds for Matching in Random-Order Streams.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Online Matching with Recourse: Random Edge Arrivals.

[BibT_eX]

[DOI]

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Near-Optimal Decremental SSSP in Dense Weighted Digraphs.

[BibT_eX]

[DOI]

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing.

[BibT_eX]

[DOI]

Thatchaphol Saranurak

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019

Distance-Preserving Graph Contractions.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2019

Online Bipartite Matching with Amortized O(log 2 n) Replacements.

[BibT_eX]

[DOI]

Jacob Holm

Eva Rotenberg

J. ACM, 2019

Decremental strongly-connected components and single-source reachability in near-linear time.

[BibT_eX]

[DOI]

Maximilian Probst

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Distributed exact weighted all-pairs shortest paths in near-linear time.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs.

[BibT_eX]

[DOI]

MohammadHossein Bateni

Vahab S. Mirrokni

Cliff Stein

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Towards a Unified Theory of Sparsification for Matching Problems.

[BibT_eX]

[DOI]

Proceedings of the 2nd Symposium on Simplicity in Algorithms, 2019

2018

Online Bipartite Matching with Amortized Replacements.

[BibT_eX]

[DOI]

Jacob Holm

Eva Rotenberg

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Incremental Topological Sort and Cycle Detection in Expected Total Time.

[BibT_eX]

[DOI]

Shiri Chechik

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Online bipartite matching with amortized $O(\log^2 n)$ replacements.

[BibT_eX]

[DOI]

Jacob Holm

Eva Rotenberg

CoRR, 2017

Deterministic Partially Dynamic Single Source Shortest Paths for Sparse Graphs.

[BibT_eX]

[DOI]

Shiri Chechik

Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Simultaneously Load Balancing for Every p-norm, With Reassignments.

[BibT_eX]

[DOI]

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

General Bounds for Incremental Maximization.

[BibT_eX]

[DOI]

Yann Disser

Martin Groß

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

Dynamic Approximate-APSP.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Decremental Approximate-APSP in Directed Graphs.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Dynamic Algorithms for Shortest Paths and Matching.

[BibT_eX]

[DOI]

PhD thesis, 2016

Maintaining Shortest Paths Under Deletions in Weighted Directed Graphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2016

Deterministic decremental single source shortest paths: beyond the o(mn) bound.

[BibT_eX]

[DOI]

Shiri Chechik

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

Faster Fully Dynamic Matchings with Small Approximation Ratios.

[BibT_eX]

[DOI]

Cliff Stein

Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

2015

Fully Dynamic Matching in Bipartite Graphs.

[BibT_eX]

[DOI]

Cliff Stein

Proceedings of the Automata, Languages, and Programming - 42nd International Colloquium, 2015

2013

Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract].

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

2012

Near linear time (1 + ε)-approximation for restricted shortest paths in undirected graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Improved Dynamic Algorithms for Maintaining Approximate Shortest Paths Under Deletions.

[BibT_eX]

[DOI]

Liam Roditty

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

A Nearly Optimal Algorithm for Approximating Replacement Paths and k Shortest Simple Paths in General Graphs.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

A nearly optimal oracle for avoiding failed vertices and edges.

[BibT_eX]

[DOI]

David R. Karger

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Fully Dynamic (2 + epsilon) Approximate All-Pairs Shortest Paths with Fast Query and Close to Linear Update Time.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Improved distance sensitivity oracles via random sampling.

[BibT_eX]

[DOI]