| Publication | Date of Publication | Type |
|---|
| Optimal energetic paths for electric cars | 2025-01-06 | Paper |
| Tight approximability of MAX 2-SAT and relatives, under UGC | 2024-11-28 | Paper |
| Optimal resizable arrays | 2024-10-21 | Paper |
| Selection from heaps, row-sorted matrices, and \(X+Y\) using soft heaps | 2024-08-26 | Paper |
| Algorithmic trade-offs for girth approximation in undirected graphs | 2024-07-19 | Paper |
| Simulating a stack using queues | 2024-07-19 | Paper |
| Finding strong components using depth-first search | 2024-06-28 | Paper |
| Minimum-cost paths for electric cars | 2024-05-29 | Paper |
| Improved girth approximation in weighted undirected graphs | 2024-05-14 | Paper |
| Optimal resizable arrays | 2024-05-14 | Paper |
| On the mysteries of MAX NAE-SAT | 2024-01-15 | Paper |
| The complexity of mean payoff games | 2023-12-12 | Paper |
| A faster deterministic exponential time algorithm for energy games and mean payoff games | 2022-07-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5091256 | 2022-07-21 | Paper |
| Pairing heaps: the forward variant | 2021-08-04 | Paper |
| Improved bounds for multipass pairing heaps and path-balanced binary search trees | 2021-08-04 | Paper |
| Public vs. private randomness in simultaneous multi-party communication complexity | 2020-02-06 | Paper |
| Faster \(k\)-SAT algorithms using biased-PPSZ | 2020-01-30 | Paper |
| A sort of an adversary | 2019-10-15 | Paper |
| Improved upper bounds for Random-Edge and Random-Jump on abstract cubes | 2019-06-20 | Paper |
| Dantzig's pivoting rule for shortest paths, deterministic MDPs, and minimum cost to time ratio cycles | 2019-06-20 | Paper |
| Discounted deterministic Markov decision processes and discounted all-pairs shortest paths | 2019-05-06 | Paper |
| A simpler implementation and analysis of Chazelle's soft heaps | 2019-05-06 | Paper |
| Efficient algorithms for the 2-gathering problem | 2019-05-06 | Paper |
| Finding even cycles even faster | 2019-04-29 | Paper |
| Adjacency labeling schemes and induced-universal graphs | 2019-01-16 | Paper |
| Hollow heaps | 2018-11-12 | Paper |
| Roundtrip spanners and roundtrip routing in directed graphs | 2018-11-05 | Paper |
| Union-find with constant time deletions | 2018-10-30 | Paper |
| Improved bounds for multipass pairing heaps and path-balanced binary search trees | 2018-06-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601879 | 2018-01-24 | Paper |
| Random-Edge Is Slower Than Random-Facet on Abstract Cubes | 2017-12-19 | Paper |
| The amortized cost of finding the minimum | 2017-10-05 | Paper |
| Collapse | 2017-09-29 | Paper |
| A subexponential lower bound for the random facet algorithm for parity games | 2017-09-29 | Paper |
| Looking for MUM and DAD: text-text comparisons do help | 2017-01-19 | Paper |
| Public vs. private randomness in simultaneous multi-party communication complexity | 2016-12-01 | Paper |
| Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems | 2016-09-29 | Paper |
| All pairs lightest shortest paths | 2016-09-29 | Paper |
| Connection caching | 2016-09-29 | Paper |
| Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs (extended abstract) | 2016-09-01 | Paper |
| A fully dynamic reachability algorithm for directed graphs with an almost linear update time | 2016-06-01 | Paper |
| Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences | 2016-04-11 | Paper |
| All pairs shortest paths using bridging sets and rectangular matrix multiplication | 2015-12-07 | Paper |
| Hollow Heaps | 2015-10-27 | Paper |
| Fast sparse matrix multiplication | 2015-09-02 | Paper |
| Melding priority queues | 2015-09-02 | Paper |
| Adjacency labeling schemes and induced-universal graphs | 2015-08-21 | Paper |
| An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm | 2015-08-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501785 | 2015-08-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501240 | 2015-08-03 | Paper |
| Detecting short directed cycles using rectangular matrix multiplication and dynamic programming | 2015-08-03 | Paper |
| A forward-backward single-source shortest paths algorithm | 2015-06-11 | Paper |
| Approximate distance oracles | 2015-02-27 | Paper |
| Deterministic rendezvous, treasure hunts and strongly universal exploration sequences | 2014-12-18 | Paper |
| Maximum matching in graphs with an excluded minor | 2014-12-18 | Paper |
| All-pairs bottleneck paths in vertex weighted graphs | 2014-12-18 | Paper |
| Discounted deterministic Markov decision processes and discounted all-pairs shortest paths | 2014-11-18 | Paper |
| Efficient algorithms for the 2-gathering problem | 2014-11-18 | Paper |
| Replacement paths and \(k\) simple shortest paths in unweighted directed graphs | 2014-09-09 | Paper |
| Listing triangles | 2014-07-01 | Paper |
| Subexponential lower bounds for randomized pivoting rules for the simplex algorithm | 2014-06-05 | Paper |
| All-pairs shortest paths in \(O(n^2)\) time with high probability | 2014-02-17 | Paper |
| Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor | 2014-02-17 | Paper |
| Soft heaps simplified | 2013-11-14 | Paper |
| Dynamic approximate all-pairs shortest paths in undirected graphs | 2012-09-12 | Paper |
| On the approximability of reachability-preserving network orientations | 2012-08-29 | Paper |
| Maximum overhang | 2012-01-01 | Paper |
| On dynamic shortest paths problems | 2011-09-20 | Paper |
| All-pairs bottleneck paths in vertex weighted graphs | 2011-03-30 | Paper |
| Lower bounds for Howard's algorithm for finding minimum mean-cost cycles | 2010-12-09 | Paper |
| A deterministic subexponential algorithm for solving parity games | 2010-08-16 | Paper |
| Spanners and emulators with sublinear distance errors | 2010-08-16 | Paper |
| Overhang | 2010-08-16 | Paper |
| A fully dynamic reachability algorithm for directed graphs with an almost linear update time | 2010-08-15 | Paper |
| Maximum overhang | 2010-08-06 | Paper |
| A Deterministic Subexponential Algorithm for Solving Parity Games | 2009-08-20 | Paper |
| Overhang | 2009-02-26 | Paper |
| An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem | 2009-01-19 | Paper |
| Approximate distance oracles | 2008-12-21 | Paper |
| Improved Dynamic Reachability Algorithms for Directed Graphs | 2008-10-28 | Paper |
| New Bounds for the Nearly Equitable Edge Coloring Problem | 2008-05-27 | Paper |
| Approximation and Online Algorithms | 2007-02-12 | Paper |
| A slightly improved sub-cubic algorithm for the all pairs shortest paths problem with real edge lengths | 2006-11-06 | Paper |
| Multicriteria global minimum cuts | 2006-10-16 | Paper |
| Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques | 2006-07-07 | Paper |
| Automata, Languages and Programming | 2006-01-10 | Paper |
| Automata, Languages and Programming | 2006-01-10 | Paper |
| Automata, Languages and Programming | 2006-01-10 | Paper |
| Algorithms and Computation | 2005-12-22 | Paper |
| Algorithms and Computation | 2005-12-22 | Paper |
| Algorithm Theory - SWAT 2004 | 2005-09-07 | Paper |
| Algorithms – ESA 2004 | 2005-08-18 | Paper |
| Algorithms – ESA 2004 | 2005-08-18 | Paper |
| Approximating MIN 2-SAT and MIN 3-SAT | 2005-06-14 | Paper |
| MAX CUT in cubic graphs | 2005-02-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828938 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828974 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4829021 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4829033 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828975 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4737518 | 2004-08-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4474206 | 2004-08-04 | Paper |
| Reachability and Distance Queries via 2-Hop Labels | 2003-09-28 | Paper |
| Combinatorial approximation algorithms for the maximum directed cut problem | 2003-09-15 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4427868 | 2003-09-14 | Paper |
| Connection caching: Model and algorithms. | 2003-08-19 | Paper |
| On the number of ANDs versus the number of ORs in monotone Boolean circuits | 2003-06-24 | Paper |
| Coloring -colorable graphs using relatively small palettes | 2003-05-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4796165 | 2003-03-02 | Paper |
| Cell identification codes for tracking mobile users | 2003-02-19 | Paper |
| Approximation algorithms for MAX-4-SAT and rounding procedures for semidefinite programs | 2002-12-01 | Paper |
| Competitive analysis of the LRFU paging algorithm | 2002-12-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4778550 | 2002-11-18 | Paper |
| Coloring \(k\)-colorable graphs using smaller palettes | 2002-10-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542575 | 2002-08-01 | Paper |
| Which bases admit non-trivial shrinkage of formulae? | 2002-07-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4537699 | 2002-07-01 | Paper |
| A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems | 2002-07-01 | Paper |
| Constructing worst case instances for semidefinite programming based approximation algorithms | 2002-04-23 | Paper |
| Which formulae shrink under random restrictions? | 2002-03-24 | Paper |
| Constructing worst case instances for semidefinite programming based approximation algorithms | 2002-01-30 | Paper |
| Optimal randomized EREW PRAM algorithms for finding spanning forests | 2001-09-20 | Paper |
| All-pairs small-stretch paths | 2001-07-23 | Paper |
| On lower bounds for selecting the median | 2001-06-21 | Paper |
| Median selection requires \((2+\varepsilon)n\) comparisons | 2001-06-21 | Paper |
| All-Pairs Almost Shortest Paths | 2000-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4250183 | 2000-02-09 | Paper |
| SOKOBAN and other motion planning problems | 2000-01-04 | Paper |
| Selecting the Median | 1999-10-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4263713 | 1999-09-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4250233 | 1999-08-16 | Paper |
| Amplification and percolation (probabilistic Boolean functions) | 1999-03-01 | Paper |
| Growth Functions and Automatic Groups | 1998-08-09 | Paper |
| Color-coding | 1998-01-28 | Paper |
| An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM | 1997-09-07 | Paper |
| Amplification by Read-Once Formulas | 1997-08-17 | Paper |
| Finding Even Cycles Even Faster | 1997-05-26 | Paper |
| Finding and counting given length cycles | 1997-03-06 | Paper |
| The smallest networks on which the Ford-Fulkerson maximum flow procedure may fail to terminate | 1997-02-28 | Paper |
| The complexity of mean payoff games on graphs | 1997-02-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4886030 | 1996-12-12 | Paper |
| Finding the \(\alpha n\)-th largest element | 1996-10-07 | Paper |
| A note on busy beavers and other creatures | 1996-08-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4875217 | 1996-04-28 | Paper |
| How Do Read-Once Formulae Shrink? | 1995-07-02 | Paper |
| Tighter Lower Bounds on the Exact Complexity of String Matching | 1995-03-27 | Paper |
| Shallow circuits and concise formulae for multiple addition and multiplication | 1994-11-29 | Paper |
| Faster Parallel String Matching via Larger Deterministic Samples | 1994-03-22 | Paper |
| The memory game | 1993-08-30 | Paper |
| Shrinkage of de Morgan formulae under restriction | 1993-06-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4036708 | 1993-05-18 | Paper |
| A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions | 1991-01-01 | Paper |
| An extension of Khrapchenko's theorem | 1991-01-01 | Paper |
| On Nečiporuk's theorem for branching programs | 1989-01-01 | Paper |
