13 citations · 29 across the 8 of their papers we have counts for
8 papers
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…
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…
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…