| Publication | Date of Publication | Type |
|---|
| On the complexity of algorithms with predictions for dynamic graph problems | 2025-11-04 | Paper |
| Electrical flows for polylogarithmic competitive oblivious routing | 2025-11-04 | Paper |
| Parametric and kinetic minimum spanning trees | 2025-10-29 | Paper |
| How can algorithms help in protecting our privacy (invited talk) | 2025-10-07 | Paper |
| Private counting of distinct elements in the turnstile model and extensions | 2025-10-06 | Paper |
| Fast dynamic cuts, distances and effective resistances via vertex sparsifiers | 2025-08-12 | Paper |
| A new deterministic algorithm for dynamic set cover | 2025-08-12 | Paper |
| Decremental single-source shortest paths on undirected graphs in near-linear total update time | 2025-08-05 | Paper |
| Fine-grained complexity lower bounds for families of dynamic graphs | 2025-06-19 | Paper |
| Dynamic approximate all-pairs shortest paths: breaking the O(mn) barrier and derandomization | 2025-05-20 | Paper |
Multiplicative auction algorithm for approximate maximum weight bipartite matching
Mathematical Programming. Series A. Series B | 2025-03-05 | Paper |
| Deterministic near-linear time minimum cut in weighted graphs | 2024-11-28 | Paper |
| Dynamically maintaining the persistent homology of time series | 2024-11-28 | Paper |
| A unifying framework for differentially private sums under continual observation | 2024-11-28 | Paper |
| Efficient data structures for incremental exact and approximate maximum flow | 2024-11-14 | Paper |
| Faster submodular maximization for several classes of matroids | 2024-11-14 | Paper |
| Dynamic maintenance of monotone dynamic programs and applications | 2024-10-08 | Paper |
| Asymptotically tight bounds on the time complexity of broadcast and its variants in dynamic networks | 2024-09-25 | Paper |
| A combinatorial cut-toggling algorithm for solving Laplacian linear systems | 2024-09-25 | Paper |
| Modern dynamic data structures (invited talk) | 2024-08-06 | Paper |
| The complexity of average-case dynamic subgraph counting | 2024-07-19 | Paper |
| Experimental evaluation of fully dynamic \(k\)-means via coresets | 2024-05-29 | Paper |
| Practical fully dynamic minimum cut algorithms | 2024-05-24 | Paper |
| Fully dynamic exact edge connectivity in sublinear time | 2024-05-14 | Paper |
| Online min-max paging | 2024-05-14 | Paper |
| Optimal fully dynamic \(k\)-center clustering for adaptive and oblivious adversaries | 2024-05-14 | Paper |
| Almost tight error bounds on differentially private continual counting | 2024-05-14 | Paper |
Recent Advances in Fully Dynamic Graph Algorithms – A Quick Reference Guide
ACM Journal of Experimental Algorithmics | 2024-04-14 | Paper |
Brief Announcement: Broadcasting Time in Dynamic Rooted Trees is Linear
Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing | 2024-03-26 | Paper |
scientific article; zbMATH DE number 7788413 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788448 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788488 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788504 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
A combinatorial cut-toggling algorithm for solving Laplacian linear systems
Algorithmica | 2023-12-13 | Paper |
A combinatorial cut-toggling algorithm for solving Laplacian linear systems
Algorithmica | 2023-12-13 | Paper |
Multiplicative auction algorithm for approximate maximum weight bipartite matching
Integer Programming and Combinatorial Optimization | 2023-11-09 | Paper |
Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles
(available as arXiv preprint) | 2023-11-02 | Paper |
Constant-time Dynamic (Δ +1)-Coloring
ACM Transactions on Algorithms | 2023-10-31 | Paper |
Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
SIAM Journal on Computing | 2023-10-26 | Paper |
scientific article; zbMATH DE number 7740897 (Why is no real title available?)
(available as arXiv preprint) | 2023-09-20 | Paper |
Fine-grained complexity lower bounds for problems in computer aided verification
Lecture Notes in Computer Science | 2023-08-10 | Paper |
Certificates and fast algorithms for biconnectivity in fully-dynamic graphs
Lecture Notes in Computer Science | 2023-05-08 | Paper |
Symbolic algorithms for graphs and Markov decision processes with fairness objectives
Computer Aided Verification | 2023-05-05 | Paper |
scientific article; zbMATH DE number 7651198 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
| Constant-time dynamic \((\Delta+1)\)-coloring | 2023-02-07 | Paper |
| Faster fully dynamic transitive closure in practice | 2023-02-07 | Paper |
scientific article; zbMATH DE number 7651196 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-07 | Paper |
scientific article; zbMATH DE number 7649915 (Why is no real title available?)
(available as arXiv preprint) | 2023-02-03 | Paper |
An algorithm for finding predecessors in integer sets
Lecture Notes in Computer Science | 2023-01-18 | Paper |
Fully dynamic 2-edge-connectivity in planar graphs
Algorithm Theory — SWAT '92 | 2022-12-09 | Paper |
Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning
Algorithm Theory — SWAT'96 | 2022-12-09 | Paper |
scientific article; zbMATH DE number 7561506 (Why is no real title available?)
(available as arXiv preprint) | 2022-07-21 | Paper |
Upper and lower bounds for fully retroactive graph problems
(available as arXiv preprint) | 2022-03-25 | Paper |
A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching
ACM Transactions on Algorithms | 2022-02-22 | Paper |
Constant-time dynamic weight approximation for minimum spanning forest
Information and Computation | 2021-11-25 | Paper |
Algorithms and conditional lower bounds for planning problems
Artificial Intelligence | 2021-11-02 | Paper |
Algorithms and conditional lower bounds for planning problems
Artificial Intelligence | 2021-11-02 | Paper |
scientific article; zbMATH DE number 7378709 (Why is no real title available?)
(available as arXiv preprint) | 2021-08-04 | Paper |
scientific article; zbMATH DE number 7378710 (Why is no real title available?)
(available as arXiv preprint) | 2021-08-04 | Paper |
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
SIAM Journal on Computing | 2021-06-29 | Paper |
| Approximating the minimum cycle mean | 2021-06-09 | Paper |
Shared-Memory Branch-and-Reduce for Multiterminal Cuts
2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) | 2021-01-27 | Paper |
Fully Dynamic <i>k</i>-Center Clustering in Low Dimensional Metrics
2021 Proceedings of the Workshop on Algorithm Engineering and Experiments (ALENEX) | 2021-01-27 | Paper |
Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
2020 Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX) | 2021-01-27 | Paper |
Memetic graph clustering
(available as arXiv preprint) | 2020-12-16 | Paper |
The State of the Art in Dynamic Graph Algorithms
SOFSEM 2018: Theory and Practice of Computer Science | 2020-10-21 | Paper |
Dynamic clustering to minimize the sum of radii
Algorithmica | 2020-10-21 | Paper |
Dynamic clustering to minimize the sum of radii
(available as arXiv preprint) | 2020-05-27 | Paper |
| Improved guarantees for vertex sparsification in planar graphs | 2020-05-27 | Paper |
The power of vertex sparsifiers in dynamic graph algorithms
(available as arXiv preprint) | 2020-05-27 | Paper |
Faster algorithms for mean-payoff parity games
(available as arXiv preprint) | 2020-05-26 | Paper |
Improved set-based symbolic algorithms for parity games
(available as arXiv preprint) | 2020-05-26 | Paper |
| Faster Parallel Multiterminal Cuts | 2020-04-24 | Paper |
Deterministic dynamic matching in \(O(1)\) update time
Algorithmica | 2020-02-28 | Paper |
Distributed edge connectivity in sublinear time
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Local flow partitioning for faster edge connectivity
SIAM Journal on Computing | 2020-01-21 | Paper |
Improved guarantees for vertex sparsification in planar graphs
SIAM Journal on Discrete Mathematics | 2020-01-10 | Paper |
A deamortization approach for dynamic spanner and dynamic maximal matching
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-10-15 | Paper |
Practical minimum cut algorithms
2018 Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments (ALENEX) | 2019-09-12 | Paper |
Quasipolynomial set-based symbolic algorithms for parity games
EPiC Series in Computing | 2019-07-04 | Paper |
A subquadratic-time algorithm for decremental single-source shortest paths
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
New amortized cell-probe lower bounds for dynamic problems
Theoretical Computer Science | 2019-06-06 | Paper |
An \(O(n^2)\) time algorithm for alternating Büchi games
(available as arXiv preprint) | 2019-05-10 | Paper |
| An \(O(n^2)\) time algorithm for alternating Büchi games | 2019-05-10 | Paper |
Practical minimum cut algorithms
ACM Journal of Experimental Algorithmics | 2019-03-27 | Paper |
Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
Journal of the ACM | 2019-02-25 | Paper |
Approximating minimum cuts under insertions
Automata, Languages and Programming | 2019-01-10 | Paper |
Incremental exact min-cut in polylogarithmic amortized update time
ACM Transactions on Algorithms | 2018-11-13 | Paper |
Incremental exact min-cut in polylogarithmic amortized update time
ACM Transactions on Algorithms | 2018-11-13 | Paper |
Sublinear-time maintenance of breadth-first spanning trees in partially dynamic networks
ACM Transactions on Algorithms | 2018-11-12 | Paper |
Local flow partitioning for faster edge connectivity
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Fully dynamic approximate maximum matching and minimum vertex cover in \(O(\log^3 n)\) worst case update time
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Maintaining minimum spanning trees in dynamic graphs
Automata, Languages and Programming | 2018-07-04 | Paper |
Deterministic fully dynamic data structures for vertex cover and matching
SIAM Journal on Computing | 2018-07-04 | Paper |
Dynamic algorithms via the primal-dual method
Information and Computation | 2018-06-14 | Paper |
| scientific article; zbMATH DE number 6876107 (Why is no real title available?) | 2018-05-29 | Paper |
Conditional hardness for sensitivity problems
(available as arXiv preprint) | 2018-05-03 | Paper |
Improved algorithms for one-pair and \(k\)-pair Streett objectives
2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science | 2018-04-23 | Paper |
Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science | 2018-04-23 | Paper |
Conditionally Optimal Algorithms for Generalized B\"uchi Games
(available as arXiv preprint) | 2018-03-21 | Paper |
| scientific article; zbMATH DE number 6850309 (Why is no real title available?) | 2018-03-15 | Paper |
scientific article; zbMATH DE number 6850309 (Why is no real title available?)
(available as arXiv preprint) | 2018-03-15 | Paper |
| Lower bounds for symbolic computation on graphs: strongly connected components, liveness, safety, and diameter | 2018-03-15 | Paper |
Lower bounds for symbolic computation on graphs: strongly connected components, liveness, safety, and diameter
(available as arXiv preprint) | 2018-03-15 | Paper |
Incremental and fully dynamic subgraph connectivity for emergency planning
(available as arXiv preprint) | 2018-03-02 | Paper |
| scientific article; zbMATH DE number 6846417 (Why is no real title available?) | 2018-03-02 | Paper |
Welfare maximization with friends-of-friends network externalities
Theory of Computing Systems | 2018-02-01 | Paper |
Graph Minors for Preserving Terminal Distances Approximately - Lower and Upper Bounds
(available as arXiv preprint) | 2017-12-19 | Paper |
Improved algorithms for parity and Streett objectives
(available as arXiv preprint) | 2017-10-12 | Paper |
Deterministic fully dynamic data structures for vertex cover and matching
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
| Faster and dynamic algorithms for maximal end-component decomposition and related graph problems in probabilistic verification | 2017-09-29 | Paper |
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
New deterministic approximation algorithms for fully dynamic matching
Proceedings of the forty-eighth annual ACM symposium on Theory of Computing | 2017-09-29 | Paper |
Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time
(available as arXiv preprint) | 2017-08-31 | Paper |
Maximizing a submodular function with viability constraints
Algorithmica | 2017-03-06 | Paper |
| Welfare maximization with friends-of-friends network externalities | 2017-01-24 | Paper |
Scheduling data transfers in a network and the set scheduling problem
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Improved data structures for fully dynamic biconnectivity
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Faster shortest-path algorithms for planar graphs
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
SIAM Journal on Computing | 2016-07-04 | Paper |
Ad exchange: envy-free auctions with mediators
Web and Internet Economics | 2016-01-08 | Paper |
Combinatorial auctions with conflict-based externalities
Web and Internet Economics | 2016-01-08 | Paper |
Online ad assignment with an ad exchange
Approximation and Online Algorithms | 2015-11-20 | Paper |
Finding 2-edge and 2-vertex strongly connected components in quadratic time
Automata, Languages, and Programming | 2015-10-27 | Paper |
Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
Automata, Languages, and Programming | 2015-10-27 | Paper |
Design of dynamic algorithms via primal-dual method
Automata, Languages, and Programming | 2015-10-27 | Paper |
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
Proceedings of the forty-seventh annual ACM symposium on Theory of Computing | 2015-08-21 | Paper |
Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
Truthful unit-demand auctions with budgets revisited
Theoretical Computer Science | 2015-02-24 | Paper |
Polynomial-time algorithms for energy games with special weight structures
Algorithmica | 2015-01-19 | Paper |
Valuation compressions in VCG-based combinatorial auctions
Web and Internet Economics | 2015-01-12 | Paper |
Limiting Price Discrimination when Selling Products with Positive Network Externalities
Web and Internet Economics | 2015-01-07 | Paper |
| Combinatorial algorithms for web search engines -- three success stories | 2014-12-18 | Paper |
Online bipartite matching with decomposable weights
Algorithms - ESA 2014 | 2014-10-08 | Paper |
Efficient and dynamic algorithms for alternating Büchi games and maximal end-component decomposition
Journal of the ACM | 2014-09-12 | Paper |
Approximating the minimum cycle mean
Theoretical Computer Science | 2014-07-25 | Paper |
Symbolic algorithms for qualitative analysis of Markov decision processes with Büchi objectives
Formal Methods in System Design | 2014-06-30 | Paper |
Maximizing a submodular function with viability constraints
Lecture Notes in Computer Science | 2013-09-17 | Paper |
Sublinear-time maintenance of breadth-first spanning tree in partially dynamic networks
Lecture Notes in Computer Science | 2013-08-07 | Paper |
Bidder optimal assignments for general utilities
Theoretical Computer Science | 2013-06-06 | Paper |
Offline file assignments for online load balancing
Information Processing Letters | 2013-04-04 | Paper |
Sponsored search, market equilibria, and the Hungarian method
Information Processing Letters | 2013-03-20 | Paper |
On multiple keyword sponsored search auctions with budgets
Automata, Languages, and Programming | 2012-11-01 | Paper |
Polynomial-time algorithms for energy games with special weight structures
Lecture Notes in Computer Science | 2012-09-25 | Paper |
| Sponsored Search, Market Equilibria, and the Hungarian Method | 2012-01-23 | Paper |
Multi-parameter mechanism design under budget and matroid constraints
Algorithms – ESA 2011 | 2011-09-16 | Paper |
Online stochastic packing applied to display ad allocation
Algorithms – ESA 2010 | 2010-09-06 | Paper |
Mechanisms for the Marriage and the Assignment Game
Lecture Notes in Computer Science | 2010-05-28 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2005-08-24 | Paper |
Algorithmic Challenges in Web Search Engines
Internet Mathematics | 2005-05-09 | Paper |
An online throughput-competitive algorithm for multicast routing and admission control
Journal of Algorithms | 2005-05-04 | Paper |
Randomized fully dynamic graph algorithms with polylogarithmic time per operation
Journal of the ACM | 2005-01-25 | Paper |
| scientific article; zbMATH DE number 2102755 (Why is no real title available?) | 2004-09-24 | Paper |
Scheduling data transfers in a network and the set scheduling problem
Journal of Algorithms | 2004-03-14 | Paper |
Scheduling multicasts on unit-capacity trees and meshes.
Journal of Computer and System Sciences | 2003-08-19 | Paper |
On the number of small cut in a graph
Information Processing Letters | 2003-06-24 | Paper |
| scientific article; zbMATH DE number 1792098 (Why is no real title available?) | 2002-10-06 | Paper |
Maintaining minimum spanning forests in dynamic graphs
SIAM Journal on Computing | 2002-04-23 | Paper |
| scientific article; zbMATH DE number 1263228 (Why is no real title available?) | 2002-01-29 | Paper |
| scientific article; zbMATH DE number 1670641 (Why is no real title available?) | 2001-11-11 | Paper |
| scientific article; zbMATH DE number 1559557 (Why is no real title available?) | 2001-02-28 | Paper |
Improved Data Structures for Fully Dynamic Biconnectivity
SIAM Journal on Computing | 2000-10-18 | Paper |
Computing Vertex Connectivity: New Bounds from Old Techniques
Journal of Algorithms | 2000-06-22 | Paper |
| scientific article; zbMATH DE number 1306878 (Why is no real title available?) | 2000-04-26 | Paper |
| scientific article; zbMATH DE number 1306899 (Why is no real title available?) | 2000-04-26 | Paper |
| scientific article; zbMATH DE number 1424324 (Why is no real title available?) | 2000-03-23 | Paper |
Exploring Unknown Environments
SIAM Journal on Computing | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1303546 (Why is no real title available?) | 2000-02-17 | Paper |
| scientific article; zbMATH DE number 1256640 (Why is no real title available?) | 1999-07-05 | Paper |
Lower bounds for fully dynamic connectivity problems in graphs
Algorithmica | 1999-07-05 | Paper |
Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology
Algorithmica | 1999-06-29 | Paper |
| scientific article; zbMATH DE number 1305434 (Why is no real title available?) | 1999-06-17 | Paper |
Average-case analysis of dynamic graph algorithms
Algorithmica | 1998-09-08 | Paper |
| Sampling to provide or to bound: With applications to fully dynamic graph algorithms | 1998-05-13 | Paper |
A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity
Journal of Algorithms | 1998-01-12 | Paper |
Faster shortest-path algorithms for planar graphs
Journal of Computer and System Sciences | 1997-10-28 | Paper |
| scientific article; zbMATH DE number 871930 (Why is no real title available?) | 1996-10-08 | Paper |
| scientific article; zbMATH DE number 910887 (Why is no real title available?) | 1996-08-22 | Paper |
Data structures for two-edge connectivity in planar graphs
Theoretical Computer Science | 1995-10-09 | Paper |
Fully dynamic biconnectivity in graphs
Algorithmica | 1995-06-19 | Paper |
Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
SIAM Journal on Computing | 1993-03-09 | Paper |
