13 citations · 28 across the 13 of their papers we have counts for
15 papers
An improved randomized algorithm for finding sinks of Acyclic Unique Sink Orientations of the binary hypercube
Thomas Dueholm Hansen, Uri Zwick
Acyclic Unique Sink Orientations (AUSOs) of the binary hypercube form an elegant abstraction of various optimization problems, ranging from linear programs whose feasibility region…
ARRIVAL: Next Stop in CLS
Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubáček +3
We study the computational complexity of ARRIVAL, a zero-player game on -vertex switch graphs introduced by Dohrau, Gärtner, Kohler, Matoušek, and Welzl. They showed that the pr…
Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
Shiri Chechik, Thomas Dueholm Hansen, Giuseppe F. Italiano +2
Connectivity related concepts are of fundamental interest in graph theory. The area has received extensive attention over four decades, but many problems remain unsolved, especiall…
Decremental Data Structures for Connectivity and Dominators in Directed Graphs
Loukas Georgiadis, Thomas Dueholm Hansen, Giuseppe F. Italiano +2
We introduce a new dynamic data structure for maintaining the strongly connected components (SCCs) of a directed graph (digraph) under edge deletions, so as to answer a rich repert…
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with nodes and edges. This problem has a long history in combinatorial optim…
Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams +1
A recent and active line of work achieves tight lower bounds for fundamental problems under the Strong Exponential Time Hypothesis (SETH). A celebrated result of Backurs and Indyk…
Hollow Heaps
Thomas Dueholm Hansen, Haim Kaplan, Robert E. Tarjan +1
We introduce the hollow heap, a very simple data structure with the same amortized efficiency as the classical Fibonacci heap. All heap operations except delete and delete-min take…
Subtree Isomorphism Revisited
Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen +2
The Subtree Isomorphism problem asks whether a given tree is contained in another given tree. The problem is of fundamental importance and has been studied since the 1960s. For som…
Errata for: A subexponential lower bound for the Random Facet algorithm for Parity Games
Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick
In Friedmann, Hansen, and Zwick (2011) we claimed that the expected number of pivoting steps performed by the Random-Facet algorithm of Kalai and of Matousek, Sharir, and Welzl is…
Random-Facet and Random-Bland require subexponential time even for shortest paths
Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick
The Random-Facet algorithm of Kalai and of Matousek, Sharir and Welzl is an elegant randomized algorithm for solving linear programs and more general LP-type problems. Its expected…
The complexity of interior point methods for solving discounted turn-based stochastic games
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen
We study the problem of solving discounted, two player, turn based, stochastic games (2TBSGs). Jurdzinski and Savani showed that 2TBSGs with deterministic transitions can be reduce…
A Faster Algorithm for Solving One-Clock Priced Timed Games
Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen
One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced time…
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick
Ye showed recently that the simplex method with Dantzig pivoting rule, as well as Howard's policy iteration algorithm, solve discounted Markov decision processes (MDPs), with a con…
On Pure and (approximate) Strong Equilibria of Facility Location Games
Thomas Dueholm Hansen, Orestis A. Telelis
We study social cost losses in Facility Location games, where selfish agents install facilities over a network and connect to them, so as to forward their local demand (express…
Approximability and parameterized complexity of minmax values
Kristoffer Arnsfelt Hansen, Thomas Dueholm Hansen, Peter Bro Miltersen +1
We consider approximating the minmax value of a multi-player game in strategic form. Tightening recent bounds by Borgs et al., we observe that approximating the value with a precis…