All-Pairs Shortest Paths with a Sublinear Additive Error (2009)
We show that for every 0 ≤ p ≤ 1 there is an O(n 2.575−p/(7.4−2.3p) ) time algorithm that given a directed graph with small positive integer weights, estimates the length of the shortest path...
SINR Diagrams: Towards Algorithmically Usable SINR Models of Wireless Networks (2008)
Avin, Chen, Emek, Yuval, Kantor, Erez, Lotker, Zvi, Peleg, David, Roditty, Liam
The rules governing the availability and quality of connections in a wireless network are described by physical models such as the signal-to-interference & noise ratio (SINR) model. For a collection...
Dynamic Connectivity: Connecting to Networks and Geometry (2008)
Chan, Timothy M., Patrascu, Mihai, Roditty, Liam
Dynamic connectivity is a well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an undirected graph,...
1 Motivation and Philosophy Research Statement (2008)
solutions for optimization problems that arise in the physical world. The physical world is constantly changing, either by objects that are inserted or deleted or by objects that move. Dealing with...
A near-linear time algorithm for computing replacement paths in planar directed graphs (2008)
Yuval Emek, David Peleg, Liam Roditty
Let G = (V (G), E(G)) be a weighted directed graph and let P be a shortest path from s to t in G. In the replacement paths problem we are required to compute for every edge e in P, the length of a...
Improved algorithms for fully dynamic geometric spanners and geometric routing (2008)
For a set S of points in R d, a t-spanner is a sparse graph on the points of S such that between any pair of points there is a path in the spanner whose total length is at most t times the Euclidean...
Liam Roditty, Mikkel Thorup, Uri Zwick
We introduce the notion of roundtrip-spanners of weighted directed graphs and describe ecient algorithms for their construction. For every integer k 1 and any > 0, we show that any directed graph...
Yuval Emek, Yuval Emek, David Peleg, Liam Roditty, A Near-linear, Time Algorithm, ...
2004 – present:
Dynamic connectivity is an extremely well-studied problem, but so far the most compelling progress has been confined to the edge-update model: maintain an understanding of connectivity in an...
On Nash Equilibria for a Network Creation Game (2006)
Albers, Susanne, Eilts, Stefan, Even-Dar, Eyal, Mansour, Yishay, Roditty, Liam
We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of...
On Nash equilibria for a network creation game (2006)
Susanne Albers, Stefan Eilts, Eyal Even-dar, Yishay Mansour, Liam Roditty
We study a network creation game recently proposed by Fabrikant, Luthra, Maneva, Papadimitriou and Shenker. In this game, each player (vertex) can create links (edges) to other players at a cost of...
A fully dynamic reachability algorithm for directed graphs with an almost linear update time (2004)
We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m+n log n) and a worst-case query time of O(n), where m is the...
A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time (2004)
We obtain a new fully dynamic algorithm for the reachability problem in directed graphs. Our algorithm has an amortized update time of O(m + n log n) and a worst-case query time of O(n), where m is...
Improved Dynamic Reachability Algorithms for Directed Graphs (2002)
We obtain several new dynamic algorithms for maintaining the transitive closure of a directed graph, and several other algorithms for answering reachability queries without explicitly maintaining a...
Improved dynamic reachability algorithms for directed graphs (2002)
Abstract We obtain several new dynamic algorithms for maintainingthe transitive closure of a directed graph, and several other algorithms for answering reachability queries without ex-plicitly...