Uri Zwick

Uri Zwick

Auto-generated profile, based on publicly available information

Uri Zwick

Tel Aviv University, Tel Aviv, Israel

Research Focus & Metrics

Academic Career Length

36Years (1991-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 March 1997 in Algorithmica
Verified
Journal Article
Closed access
PDF file
NAN. Alon
N. Alon
RYRaphael Yuster
Raphael Yuster
UZU. Zwick
U. Zwick

1 May 2002 in Journal of the ACM
Verified
Journal Article
Open access
UZUri Zwick
Uri Zwick
We present two new algorithms for solving the All Pairs Shortest Paths (APSP) problem for weighted directed graphs. Both algorithms use fast matrix multiplication algorithms.The first algorithm solves the APSP problem for weighted directed graphs in which the edge weights are integers of small absolute value in Õ ( n 2+μ ) time, where μ satisfies the equation ω(1, μ, 1) = 1 + 2μ and ω(1, μ, 1) is the exponent of the multiplication of an n × n μ matrix by an n μ × n matrix. Currently, the best available bounds on ω(1, μ, 1), obtained by Coppersmith, imply that μ < 0.575. The running time of our algorithm is therefore O ( n 2.575 ). Our algorithm improves on the Õ ( n (3c+ω)/2 ) time algorithm, where ω = ω(1, 1, 1) < 2.376 is the usual exponent of matrix multiplication, obtained by Alon et al., whose running time is only known to be O ( n 2.688 ).The second algorithm solves the APSP problem almost exactly for directed graphs with arbitrary nonnegative real weights. The algorithm runs in Õ(( n ω /ϵ) log( W /ϵ)) time, where ϵ > 0 is an error parameter and W is the largest edge weight in the graph, after the edge weights are scaled so that the smallest non-zero edge weight in the graph is 1. It returns estimates of all the distances in the graph with a stretch of at most 1 + ϵ. Corresponding paths can also be found efficiently.

3 July 2001
Verified
Conference Paper
Open access
MTMikkel Thorup
Mikkel Thorup
UZUri Zwick
Uri Zwick
We describe several compact routing schemes for general weighted undirected networks. Our schemes are simple and easy to implement. The routing tables stored at the nodes of the network are all very small. The headers attached to the routed messages, including the name of the destination, are extremely short. The routing decision at each node takes constant time. Yet, the stretch of these routing schemes, i.e., the worst ratio between the cost of the path on which a packet is routed and the cost of the cheapest path from source to destination, is a small constant. Our schemes achieve a near-optimal tradeoff between the size of the routing tables used and the resulting stretch. More specifically, we obtain:A routing scheme that uses only O (n 1/2) bits of memory at each node of an n-node network that has stretch 3. The space is optimal, up to logarithmic factors, in the sense that every routing scheme with stretch n2), and every routing scheme with stretch n3/2). The headers used are only (1 + &Ogr;(1)) log2 n-bits long and each routing decision takes constant time. A variant of this scheme with [log2 n] -bit headers makes routing decisions in &Ogr;(log log n) time.Also, for every integer k 2, a general handshaking based routing scheme that uses O (n1/k) bits of memory at each node that has stretch 2k - 1. A conjecture of Erdös from 1963, settled for k = 3, 5, implies that the routing tables are of near-optimal size relative to the stretch. The handshaking is similar in spirit to a DNS lookup in TCP/IP. Headers are &Ogr;(log2 n) bits long and each routing decision takes constant time. Without handshaking, the stretch of the scheme increases to 4k — 5. One ingredient used to obtain the routing schemes mentioned above, may be of independent practical and theoretical interest:A shortest path routing scheme for trees of arbitrary degree and diameter that assigns each vertex of an n-node tree a (1 + &Ogr;(1)) log2 n-bit label. Given the label of a source node and the label of a destination it is possible to compute, in constant time, the port number of the edge from the source that heads in the direction of the destination.The general scheme for k 2 also uses a clustering technique introduced recently by the authors. The clusters obtained using this technique induce a sparse and low stretch tree cover of the network. This essentially reduces routing in general networks into routing problems in trees that could be solved using the above technique.

3 March 2010 in Algorithmica
Verified
Journal Article
Closed access
PDF file
LRLiam Roditty
Liam Roditty
UZUri Zwick
Uri Zwick

6 July 2001
Verified
Conference Paper
Open access
PDF file
MTMikkel Thorup
Mikkel Thorup
UZUri Zwick
Uri Zwick
Let G=(V,E) be an undirected weighted graph with |V|=n and |E|=m. Let k\ge 1 be an integer. We show that G=(V,E) can be preprocessed in O(kmn^{1/k}) expected time, constructing a data structure of size O(kn^{1+1/k}), such that any subsequent distance query can be answered, approximately, in O(k) time. The approximate distance returned is of stretch at most 2k-1, i.e., the quotient obtained by dividing the estimated distance by the actual distance lies between 1 and 2k-1. We show that a 1963 girth conjecture of Erd{\H{o}}s, implies that &ohgr(n^{1+1/k}) space is needed in the worst case for any real stretch strictly smaller than 2k+1. The space requirement of our algorithm is, therefore, essentially optimal. The most impressive feature of our data structure is its constant query time, hence the name ``oracle''. Previously, data structures that used only O(n^{1+1/k}) space had a query time of &ohgr(n^{1/k}) and a slightly larger, non-optimal, stretch. Our algorithms are extremely simple and easy to implement efficiently. They also provide faster constructions of sparse spanners of weighted graphs, and improved tree covers and distance labelings of weighted or unweighted graphs.}