13 citations · 40 across the 21 of their papers we have counts for
19 papers · 1 filter
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…
Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs
Uri Zwick
We give a concise description and an improved analysis of the Random-Action-Removal algorithm for solving 2-player, 0-sum, turn-based, possibly infinite duration, stochastic or non…
Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
The input to the Multiway Cut problem is a weighted undirected graph, with nonnegative edge weights, and designated terminals. The goal is to partition the vertices of the grap…
Improved girth approximation in weighted undirected graphs
Avi Kadria, Liam Roditty, Aaron Sidford +2
Let be a -node -edge weighted undirected graph, where is a real \emph{length} function defined on its edges, and let den…
Minimum-cost paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +2
An electric car equipped with a battery of a finite capacity travels on a road network with an infrastructure of charging stations. Each charging station has a possibly different c…
Optimal energetic paths for electric cars
Dani Dorfman, Haim Kaplan, Robert E. Tarjan +1
A weighted directed graph , where and , describes a road network in which an electric car can roam. An arc models a road segment co…
Optimal resizable arrays
Robert E. Tarjan, Uri Zwick
A \emph{resizable array} is an array that can \emph{grow} and \emph{shrink} by the addition or removal of items from its end, or both its ends, while still supporting constant-time…
Finding Strong Components Using Depth-First Search
Robert E. Tarjan, Uri Zwick
We survey three algorithms that use depth-first search to find the strong components of a directed graph in linear time: (1) Tarjan's algorithm; (2) a cycle-finding algorithm; and…
Improved bounds for multipass pairing heaps and path-balanced binary search trees
Dani Dorfman, Haim Kaplan, László Kozma +2
We revisit multipass pairing heaps and path-balanced binary search trees (BSTs), two classical algorithms for data structure maintenance. The pairing heap is a simple and efficient…
Selection from heaps, row-sorted matrices and using soft heaps
Haim Kaplan, László Kozma, Or Zamir +1
We use soft heaps to obtain simpler optimal algorithms for selecting the -th smallest item, and the set of~ smallest items, from a heap-ordered tree, from a collection of sor…
Pairing heaps: the forward variant
Dani Dorfman, Haim Kaplan, László Kozma +1
The pairing heap is a classical heap data structure introduced in 1986 by Fredman, Sedgewick, Sleator, and Tarjan. It is remarkable both for its simplicity and for its excellent pe…
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…
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…
Fibonacci Heaps Revisited
Haim Kaplan, Robert E. Tarjan, Uri Zwick
The Fibonacci heap is a classic data structure that supports deletions in logarithmic amortized time and all other heap operations in O(1) amortized time. We explore the design spa…
A forward-backward single-source shortest paths algorithm
David B. Wilson, Uri Zwick
We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithm only scan edges forward, t…
Adjacency labeling schemes and induced-universal graphs
Stephen Alstrup, Haim Kaplan, Mikkel Thorup +1
We describe a way of assigning labels to the vertices of any undirected graph on up to vertices, each composed of bits, such that given the labels of two vertices, a…
Coloring k-colorable graphs using relatively small palettes
Eran Halperin, Ram Nathaniel, Uri Zwick
We obtain the following new coloring results: * A 3-colorable graph on vertices with maximum degree~ can be colored, in polynomial time, using $O((Δ\logΔ)^{1/3} \cdot\log{n}…
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
Uri Zwick
We present two new algorithms for solving the {\em All Pairs Shortest Paths} (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.…