| 2009 |
|---|
| 133 | EE | Haim Kaplan,
Uri Zwick:
A simpler implementation and analysis of Chazelle's soft heaps.
SODA 2009: 477-485 |
| 132 | EE | Omid Madani,
Mikkel Thorup,
Uri Zwick:
Discounted deterministic Markov decision processes and discounted all-pairs shortest paths.
SODA 2009: 958-967 |
| 131 | EE | Alon Shalita,
Uri Zwick:
Efficient algorithms for the 2-gathering problem.
SODA 2009: 96-105 |
| 2008 |
|---|
| 130 | EE | Uri Zwick:
Simple Stochastic Games, Mean Payoff Games, Parity Games.
CSR 2008: 29 |
| 129 | EE | Mike Paterson,
Yuval Peres,
Mikkel Thorup,
Peter Winkler,
Uri Zwick:
Maximum overhang.
SODA 2008: 756-765 |
| 128 | EE | Alexander Medvedovsky,
Vineet Bafna,
Uri Zwick,
Roded Sharan:
An Algorithm for Orienting Graphs Based on Cause-Effect Pairs and Its Applications to Orienting Protein Networks.
WABI 2008: 222-232 |
| 127 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color Coding.
Encyclopedia of Algorithms 2008 |
| 126 | EE | Liam Roditty,
Mikkel Thorup,
Uri Zwick:
Roundtrip spanners and roundtrip routing in directed graphs.
ACM Transactions on Algorithms 4(3): (2008) |
| 125 | EE | Liam Roditty,
Uri Zwick:
Improved Dynamic Reachability Algorithms for Directed Graphs.
SIAM J. Comput. 37(5): 1455-1471 (2008) |
| 124 | EE | Marcin Jurdzinski,
Mike Paterson,
Uri Zwick:
A Deterministic Subexponential Algorithm for Solving Parity Games.
SIAM J. Comput. 38(4): 1519-1532 (2008) |
| 2007 |
|---|
| 123 | EE | Xuzhen Xie,
Mutsunori Yagiura,
Takao Ono,
Tomio Hirata,
Uri Zwick:
New Bounds for the Nearly Equitable Edge Coloring Problem.
ISAAC 2007: 280-291 |
| 122 | EE | Raphael Yuster,
Uri Zwick:
Maximum matching in graphs with an excluded minor.
SODA 2007: 108-117 |
| 121 | EE | Amnon Ta-Shma,
Uri Zwick:
Deterministic rendezvous, treasure hunts and strongly universal exploration sequences.
SODA 2007: 599-608 |
| 120 | EE | Asaf Shapira,
Raphael Yuster,
Uri Zwick:
All-pairs bottleneck paths in vertex weighted graphs.
SODA 2007: 978-985 |
| 2006 |
|---|
| 119 | | Josep Díaz,
Klaus Jansen,
José D. P. Rolim,
Uri Zwick:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings
Springer 2006 |
| 118 | EE | Marcin Jurdzinski,
Mike Paterson,
Uri Zwick:
A deterministic subexponential algorithm for solving parity games.
SODA 2006: 117-123 |
| 117 | EE | Mike Paterson,
Uri Zwick:
Overhang.
SODA 2006: 231-240 |
| 116 | EE | Mikkel Thorup,
Uri Zwick:
Spanners and emulators with sublinear distance errors.
SODA 2006: 802-809 |
| 115 | EE | Ran Mendelson,
Robert Endre Tarjan,
Mikkel Thorup,
Uri Zwick:
Melding priority queues.
ACM Transactions on Algorithms 2(4): 535-556 (2006) |
| 114 | EE | Amitai Armon,
Uri Zwick:
Multicriteria Global Minimum Cuts.
Algorithmica 46(1): 15-26 (2006) |
| 113 | EE | Uri Zwick:
A Slightly Improved Sub-Cubic Algorithm for the All PairsShortest Paths Problem with Real Edge Lengths.
Algorithmica 46(2): 181-192 (2006) |
| 2005 |
|---|
| 112 | EE | Adi Avidor,
Uri Zwick:
Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT.
APPROX-RANDOM 2005: 14-25 |
| 111 | EE | Raphael Yuster,
Uri Zwick:
Answering distance queries in directed graphs using fast matrix multiplication.
FOCS 2005: 389-396 |
| 110 | EE | Liam Roditty,
Uri Zwick:
Replacement Paths and k Simple Shortest Paths in Unweighted Directed Graphs.
ICALP 2005: 249-260 |
| 109 | EE | Liam Roditty,
Mikkel Thorup,
Uri Zwick:
Deterministic Constructions of Approximate Distance Oracles and Spanners.
ICALP 2005: 261-272 |
| 108 | EE | Stephen Alstrup,
Inge Li Gørtz,
Theis Rauhe,
Mikkel Thorup,
Uri Zwick:
Union-Find with Constant Time Deletions.
ICALP 2005: 78-89 |
| 107 | EE | Adi Avidor,
Ido Berkovitch,
Uri Zwick:
Improved Approximation Algorithms for MAX NAE-SAT and MAX SAT.
WAOA 2005: 27-40 |
| 106 | EE | Raphael Yuster,
Uri Zwick:
Fast sparse matrix multiplication.
ACM Transactions on Algorithms 1(1): 2-13 (2005) |
| 105 | EE | Mikkel Thorup,
Uri Zwick:
Approximate distance oracles.
J. ACM 52(1): 1-24 (2005) |
| 104 | EE | Adi Avidor,
Uri Zwick:
Approximating MIN 2-SAT and MIN 3-SAT.
Theory Comput. Syst. 38(3): 329-345 (2005) |
| 2004 |
|---|
| 103 | EE | Liam Roditty,
Uri Zwick:
On Dynamic Shortest Paths Problems.
ESA 2004: 580-591 |
| 102 | EE | Raphael Yuster,
Uri Zwick:
Fast Sparse Matrix Multiplication.
ESA 2004: 604-615 |
| 101 | EE | Liam Roditty,
Uri Zwick:
Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs.
FOCS 2004: 499-508 |
| 100 | EE | Amitai Armon,
Uri Zwick:
Multicriteria Global Minimum Cuts.
ISAAC 2004: 65-76 |
| 99 | EE | Uri Zwick:
A Slightly Improved Sub-Cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths.
ISAAC 2004: 921-932 |
| 98 | EE | Raphael Yuster,
Uri Zwick:
Detecting short directed cycles using rectangular matrix multiplication and dynamic programming.
SODA 2004: 254-260 |
| 97 | EE | Ran Mendelson,
Mikkel Thorup,
Uri Zwick:
Meldable RAM priority queues and minimum directed spanning trees.
SODA 2004: 40-48 |
| 96 | EE | Liam Roditty,
Uri Zwick:
A fully dynamic reachability algorithm for directed graphs with an almost linear update time.
STOC 2004: 184-191 |
| 95 | EE | Ran Mendelson,
Robert Endre Tarjan,
Mikkel Thorup,
Uri Zwick:
Melding Priority Queues.
SWAT 2004: 223-235 |
| 94 | EE | Eran Halperin,
Dror Livnat,
Uri Zwick:
MAX CUT in cubic graphs.
J. Algorithms 53(2): 169-185 (2004) |
| 2003 |
|---|
| 93 | | Giuseppe Di Battista,
Uri Zwick:
Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings
Springer 2003 |
| 92 | EE | Edith Cohen,
Haim Kaplan,
Uri Zwick:
Connection caching: model and algorithms.
J. Comput. Syst. Sci. 67(1): 92-126 (2003) |
| 91 | EE | Edith Cohen,
Eran Halperin,
Haim Kaplan,
Uri Zwick:
Reachability and Distance Queries via 2-Hop Labels.
SIAM J. Comput. 32(5): 1338-1355 (2003) |
| 2002 |
|---|
| 90 | EE | Liam Roditty,
Uri Zwick:
Improved Dynamic Reachability Algorithms for Directed Graphs.
FOCS 2002: 679- |
| 89 | EE | Michael Lewin,
Dror Livnat,
Uri Zwick:
Improved Rounding Techniques for the MAX 2-SAT and MAX DI-CUT Problems.
IPCO 2002: 67-82 |
| 88 | EE | Adi Avidor,
Uri Zwick:
Approximating MIN k-SAT.
ISAAC 2002: 465-475 |
| 87 | EE | Uri Zwick:
Jenga.
SODA 2002: 243-246 |
| 86 | EE | Uri Zwick:
Computer assisted proof of optimal approximability results.
SODA 2002: 496-505 |
| 85 | EE | Eran Halperin,
Dror Livnat,
Uri Zwick:
MAX CUT in cubic graphs.
SODA 2002: 506-513 |
| 84 | EE | Liam Roditty,
Mikkel Thorup,
Uri Zwick:
Roundtrip spanners and roundtrip routing in directed graphs.
SODA 2002: 844-851 |
| 83 | EE | Edith Cohen,
Eran Halperin,
Haim Kaplan,
Uri Zwick:
Reachability and distance queries via 2-hop labels.
SODA 2002: 937-946 |
| 82 | EE | Edith Cohen,
Haim Kaplan,
Uri Zwick:
Competitive Analysis of the LRFU Paging Algorithm.
Algorithmica 33(4): 511-516 (2002) |
| 81 | EE | Uri Zwick:
All pairs shortest paths using bridging sets and rectangular matrix multiplication.
J. ACM 49(3): 289-317 (2002) |
| 80 | EE | Eran Halperin,
Ram Nathaniel,
Uri Zwick:
Coloring k-colorable graphs using relatively small palettes.
J. Algorithms 45(1): 72-90 (2002) |
| 79 | EE | Eran Halperin,
Uri Zwick:
A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems.
Random Struct. Algorithms 20(3): 382-402 (2002) |
| 78 | | Zohar Naor,
Hanoch Levy,
Uri Zwick:
Cell Identification Codes for Tracking Mobile Users.
Wireless Networks 8(1): 73-84 (2002) |
| 2001 |
|---|
| 77 | EE | Uri Zwick:
Exact and Approximate Distances in Graphs - A Survey.
ESA 2001: 33-48 |
| 76 | EE | Uri Zwick:
Semidefinite Programming Based Approximation Algorithms.
FSTTCS 2001: 57 |
| 75 | EE | Eran Halperin,
Uri Zwick:
A Unified Framework for Obtaining Improved Approximation Algorithms for Maximum Graph Bisection Problems.
IPCO 2001: 210-225 |
| 74 | EE | Eran Halperin,
Uri Zwick:
Combinatorial approximation algorithms for the maximum directed cut problem.
SODA 2001: 1-7 |
| 73 | EE | Eran Halperin,
Ram Nathaniel,
Uri Zwick:
Coloring k-colorable graphs using smaller palettes.
SODA 2001: 319-326 |
| 72 | EE | Hana Chockler,
Uri Zwick:
Which formulae shrink under random restrictions?
SODA 2001: 702-708 |
| 71 | EE | Noga Alon,
Benny Sudakov,
Uri Zwick:
Constructing worst case instances for semidefinite programming based approximation algorithms.
SODA 2001: 92-100 |
| 70 | EE | Mikkel Thorup,
Uri Zwick:
Compact routing schemes.
SPAA 2001: 1-10 |
| 69 | EE | Mikkel Thorup,
Uri Zwick:
Approximate distance oracles.
STOC 2001: 183-192 |
| 68 | EE | Edith Cohen,
Haim Kaplan,
Uri Zwick:
Competitive Analysis of the LRFU Paging Algorithm.
WADS 2001: 148-154 |
| 67 | EE | Eran Halperin,
Ram Nathaniel,
Uri Zwick:
Coloring k-colorable graphs using relatively small palettes
CoRR cs.DS/0105029: (2001) |
| 66 | EE | Hana Chockler,
Uri Zwick:
Which bases admit non-trivial shrinkage of formulae?
Computational Complexity 10(1): 28-40 (2001) |
| 65 | | Edith Cohen,
Uri Zwick:
All-Pairs Small-Stretch Paths.
J. Algorithms 38(2): 335-353 (2001) |
| 64 | | Shay Halperin,
Uri Zwick:
Optimal Randomized EREW PRAM Algorithms for Finding Spanning Forests.
J. Algorithms 39(1): 1-46 (2001) |
| 63 | | Eran Halperin,
Uri Zwick:
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs.
J. Algorithms 40(2): 184-211 (2001) |
| 62 | EE | Dorit Dor,
Johan Håstad,
Staffan Ulfberg,
Uri Zwick:
On Lower Bounds for Selecting the Median.
SIAM J. Discrete Math. 14(3): 299-311 (2001) |
| 61 | EE | Dorit Dor,
Uri Zwick:
Median Selection Requires (2+epsilon)n Comparisons.
SIAM J. Discrete Math. 14(3): 312-325 (2001) |
| 60 | EE | Noga Alon,
Benny Sudakov,
Uri Zwick:
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms.
SIAM J. Discrete Math. 15(1): 58-72 (2001) |
| 2000 |
|---|
| 59 | EE | Edith Cohen,
Haim Kaplan,
Uri Zwick:
Connection caching under vaious models of communication.
SPAA 2000: 54-63 |
| 58 | EE | Uri Zwick:
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
CoRR cs.DS/0008011: (2000) |
| 57 | EE | Uri Zwick:
All Pairs Shortest Paths using Bridging Sets and Rectangular Matrix Multiplication
Electronic Colloquium on Computational Complexity (ECCC) 7(60): (2000) |
| 56 | | Dorit Dor,
Shay Halperin,
Uri Zwick:
All-Pairs Almost Shortest Paths.
SIAM J. Comput. 29(5): 1740-1759 (2000) |
| 1999 |
|---|
| 55 | EE | Avi Shoshan,
Uri Zwick:
All Pairs Shortest Paths in Undirected Graphs with Integer Weights.
FOCS 1999: 605-615 |
| 54 | EE | Eran Halperin,
Uri Zwick:
Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs.
IPCO 1999: 202-217 |
| 53 | EE | Uri Zwick:
All Pairs Lightest Shortest Paths.
STOC 1999: 61-69 |
| 52 | EE | Edith Cohen,
Haim Kaplan,
Uri Zwick:
Connection Caching.
STOC 1999: 612-621 |
| 51 | EE | Uri Zwick:
Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems.
STOC 1999: 679-687 |
| 50 | | Dorit Dor,
Uri Zwick:
SOKOBAN and other motion planning problems.
Comput. Geom. 13(4): 215-228 (1999) |
| 49 | | Ashwin Nayak,
Alistair Sinclair,
Uri Zwick:
Spatial Codes and the Hardness of String Folding Problems.
Journal of Computational Biology 6(1): 13-36 (1999) |
| 48 | | Dorit Dor,
Uri Zwick:
Selecting the Median.
SIAM J. Comput. 28(5): 1722-1758 (1999) |
| 1998 |
|---|
| 47 | EE | Uri Zwick:
All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms.
FOCS 1998: 310-319 |
| 46 | | Uri Zwick:
Approximation Algorithms for Constraint Satisfaction Problems Involving at Most Three Variables per Constraint.
SODA 1998: 201-210 |
| 45 | | Ashwin Nayak,
Alistair Sinclair,
Uri Zwick:
Spatial Codes and the Hardness of String Folding Problems (Extended Abstract).
SODA 1998: 639-648 |
| 44 | EE | Uri Zwick:
Finding Almost-Satisfying Assignments.
STOC 1998: 551-560 |
| 1997 |
|---|
| 43 | EE | Howard J. Karloff,
Uri Zwick:
A 7/8-Approximation Algorithm for MAX 3SAT?
FOCS 1997: 406-415 |
| 42 | EE | Gábor Tardos,
Uri Zwick:
The Communication Complexity of the Universal Relation.
IEEE Conference on Computational Complexity 1997: 247-259 |
| 41 | | Edith Cohen,
Uri Zwick:
All-Pairs Small-Stretch Paths.
SODA 1997: 93-102 |
| 40 | | Noga Alon,
Raphael Yuster,
Uri Zwick:
Finding and Counting Given Length Cycles.
Algorithmica 17(3): 209-223 (1997) |
| 39 | EE | Dorit Dor,
Shay Halperin,
Uri Zwick:
All Pairs Almost Shortest Paths
Electronic Colloquium on Computational Complexity (ECCC) 4(40): (1997) |
| 38 | | Moshe Dubiner,
Uri Zwick:
Amplification by Read-Once Formulas.
SIAM J. Comput. 26(1): 15-38 (1997) |
| 37 | EE | Raphael Yuster,
Uri Zwick:
Finding Even Cycles Even Faster.
SIAM J. Discrete Math. 10(2): 209-222 (1997) |
| 1996 |
|---|
| 36 | | Dorit Dor,
Uri Zwick:
Median Selection Requires (2+epsilon)n Comparisons.
FOCS 1996: 125-134 |
| 35 | | Dorit Dor,
Shay Halperin,
Uri Zwick:
All Pairs Almost Shortest Paths.
FOCS 1996: 452-461 |
| 34 | | Shay Halperin,
Uri Zwick:
Optimal randomized EREW PRAM Algorithms for Finding Spanning Forests and for other Basic Graph Connectivity Problems.
SODA 1996: 438-447 |
| 33 | | Dorit Dor,
Uri Zwick:
Finding The alpha n-Th Largest Element.
Combinatorica 16(1): 41-58 (1996) |
| 32 | EE | Uri Zwick:
On the Number of ANDs Versus the Number of ORs in Monotone Boolean Circuits.
Inf. Process. Lett. 59(1): 29-30 (1996) |
| 31 | | Shay Halperin,
Uri Zwick:
An Optimal Randomised Logarithmic Time Connectivity Algorithm for the EREW PRAM.
J. Comput. Syst. Sci. 53(3): 395-416 (1996) |
| 30 | | Amir M. Ben-Amram,
Bryant A. Julstrom,
Uri Zwick:
A Note on Busy Beavers and Other Creatures.
Mathematical Systems Theory 29(4): 375-386 (1996) |
| 29 | EE | Uri Zwick,
Mike Paterson:
The Complexity of Mean Payoff Games on Graphs.
Theor. Comput. Sci. 158(1&2): 343-359 (1996) |
| 1995 |
|---|
| 28 | | Uri Zwick,
Mike Paterson:
The Complexity of Mean Payoff Games.
COCOON 1995: 1-10 |
| 27 | | Mike Paterson,
Shlomit Tassa,
Uri Zwick:
Looking for MUM and DAD: Text-Text Comparisons Do Help.
FSTTCS 1995: 1-10 |
| 26 | | Tal Goldberg,
Uri Zwick:
Optimal deterministic approximate parallel prefix sums and their applications.
ISTCS 1995: 220-228 |
| 25 | | Dorit Dor,
Uri Zwick:
Finding percentile elements.
ISTCS 1995: 88-97 |
| 24 | | Dorit Dor,
Uri Zwick:
Selecting the Median.
SODA 1995: 28-37 |
| 23 | EE | Dorit Dor,
Uri Zwick:
Selecting the Median
Electronic Colloquium on Computational Complexity (ECCC) 2(31): (1995) |
| 22 | EE | Uri Zwick,
Mike Paterson:
The Complexity of Mean Payoff Games on Graphs
Electronic Colloquium on Computational Complexity (ECCC) 2(40): (1995) |
| 21 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color-Coding.
J. ACM 42(4): 844-856 (1995) |
| 20 | | Richard Cole,
Ramesh Hariharan,
Mike Paterson,
Uri Zwick:
Tighter Lower Bounds on the Exact Complexity of String Matching.
SIAM J. Comput. 24(1): 30-45 (1995) |
| 19 | EE | Uri Zwick:
The Smallest Networks on Which the Ford-Fulkerson Maximum Flow Procedure may Fail to Terminate.
Theor. Comput. Sci. 148(1): 165-170 (1995) |
| 1994 |
|---|
| 18 | | Noga Alon,
Raphael Yuster,
Uri Zwick:
Finding and Counting Given Length Cycles (Extended Abstract).
ESA 1994: 354-364 |
| 17 | | Raphael Yuster,
Uri Zwick:
Finding Even Cycles Even Faster.
ICALP 1994: 532-543 |
| 16 | EE | Shay Halperin,
Uri Zwick:
An Optimal Randomized Logarithmic Time Connectivity algorithm for the EREW PRAM (Extended Abstract).
SPAA 1994: 1-10 |
| 15 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color-coding: a new method for finding simple paths, cycles and other small subgraphs within large graphs.
STOC 1994: 326-335 |
| 14 | | Moshe Dubiner,
Uri Zwick:
How Do Read-Once Formulae Shrink?
Combinatorics, Probability & Computing 3: 455-469 (1994) |
| 13 | EE | Noga Alon,
Raphael Yuster,
Uri Zwick:
Color-Coding
Electronic Colloquium on Computational Complexity (ECCC) 1(9): (1994) |
| 12 | | Tal Goldberg,
Uri Zwick:
Faster Parallel String Matching via Larger Deterministic Samples.
J. Algorithms 16(2): 295-308 (1994) |
| 1993 |
|---|
| 11 | | Richard Cole,
Ramesh Hariharan,
Mike Paterson,
Uri Zwick:
Which Patterns are Hard to Find?
ISTCS 1993: 59-68 |
| 10 | | Mike Paterson,
Uri Zwick:
Shallow Circuits and Concise Formulae for Multiple Addition and Multiplication.
Computational Complexity 3: 262-291 (1993) |
| 9 | | Mike Paterson,
Uri Zwick:
Shrinkage of de Morgan Formulae under Restriction.
Random Struct. Algorithms 4(2): 135-150 (1993) |
| 8 | | Uri Zwick,
Mike Paterson:
The Memory Game.
Theor. Comput. Sci. 110(1): 169-196 (1993) |
| 1992 |
|---|
| 7 | | Moshe Dubiner,
Uri Zwick:
Amplification and Percolation
FOCS 1992: 258-267 |
| 6 | | Mike Paterson,
Uri Zwick:
Shallow Multiplication Circuits and Wise Financial Investments
STOC 1992: 429-437 |
| 1991 |
|---|
| 5 | | Mike Paterson,
Uri Zwick:
Shrinkage of de~Morgan formulae under restriction
FOCS 1991: 324-333 |
| 4 | | Uri Zwick:
An Extension of Khrapchenko's Theorem.
Inf. Process. Lett. 37(4): 215-217 (1991) |
| 3 | | Uri Zwick:
A 4n Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions.
SIAM J. Comput. 20(3): 499-505 (1991) |
| 1990 |
|---|
| 2 | | Mike Paterson,
Nicholas Pippenger,
Uri Zwick:
Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions
FOCS 1990: 642-650 |
| 1989 |
|---|
| 1 | | Noga Alon,
Uri Zwick:
On Neciporuk's Theorem for Branching Programs.
Theor. Comput. Sci. 64(3): 331-342 (1989) |
