List of Publications, Uzi Vishkin
ARTICLES IN JOURNALS

Y. Shiloach and U. Vishkin.
Finding the maximum, merging and sorting in a parallel computation model.
J. of Algorithms, 2 (1981), 88102.

Y. Shiloach and U. Vishkin.
An O(log n) parallel connectivity algorithm.
J. of Algorithms, 3 (1982), 5767.

R. BarYehuda and U. Vishkin.
Complexity of finding k pathfree dominating sets in graphs.
Information Processing Letters, 14, 5 (1982), 228232.

U. Vishkin.
An efficient distributed orientation algorithm.
IEEE Trans. on Information Theory IT29, 4 (July 1983), 624629.

Y. Shiloach, U. Vishkin and S. Zaks.
Golden ratios in pair covering problems.
Discrete Mathematics, 41 (1982), 5765.

Y. Shiloach and U. Vishkin.
An O((n**2)log n) parallel maxflow algorithm.
J. of Algorithms, 3 (1982), 128146.

U. Vishkin.
Implementation of simultaneous memory address access
in models that forbid it.
J. of Algorithms, 4 (March 1983), 4550.

W. Paul, U. Vishkin and H. Wagener.
Parallel computation on 23 trees.
RAIROTheoretical Informatics 17,4 (1983), 397404.

U. Vishkin and A. Wigderson.
Dynamic parallel memories.
Information and Control 56,3 (1983), 174182.

L.J. Stockmeyer and U. Vishkin.
Simulation of parallel random access machines by circuits.
SIAM J. Computing 13,2 (1984), 409422.

A.K. Chandra, L.J. Stockmeyer and U. Vishkin.
Constant depth reducibility.
SIAM J. Computing 13,2 (1984), 423439.

Y. Gurevich, L. J. Stockmeyer and U. Vishkin.
Solving NPhard problems on graphs that are almost trees with
applications to facility location problems.
J. of ACM 31,3 (1984), 459473.

U. Vishkin.
An optimal parallel connectivity algorithm.
Discrete Applied Mathematics 9 (1984), 197207.

U. Vishkin.
ParallelDesign DistributedImplementation
(PDDI) General Purpose Computer.
Theoretical Computer Science 32 (1984), 157172.

K. Mehlhorn and U. Vishkin.
Randomized and deterministic simulations of PRAMs by
parallel machines with restricted granularity of parallel memories.
Acta Informatica 21 (1984), 339374.

M.J. Atallah and U. Vishkin.
Finding Euler tours in parallel.
J. of Computer Systems and Sciences 29, 3 (1984), 330337.

D. Coppersmith and U. Vishkin.
Solving NPhard problems on 'almost trees': Vertex Cover.
Discrete Applied Mathematics 10 (1985), 2745.

U. Vishkin and A. Wigderson.
Tradeoffs between depth and width in parallel computation.
SIAM J. Computing 14,2 (1985), 303314.

I. BarOn and U. Vishkin.
Optimal parallel generation of a computation tree form.
ACM Tran. on Prog. Lang. and Sys. 7,2 (1985), 348357.

U. Vishkin.
On efficient parallel strong orientation.
Information Processing Letters 20 (1985), 235240.

Y. Perl and U. Vishkin.
Efficient implementation of a shifting algorithm.
Discrete Applied Mathematics 12,1 (1985), 7180.

R.E. Tarjan and U. Vishkin.
An efficient parallel biconnectivity algorithm.
SIAM J. Computing 14,4 (1985), 862874.

G.M Landau, U. Vishkin and R. Nussinov.
An efficient string matching algorithm with k differences for
nucleotide and amino acid sequences.
Nucleic Acids Research (Computer Issue) 14,1 (1986), 3146.

U. Vishkin.
Optimal parallel pattern matching in strings.
Information and Control 67,13 (1985), 91113.

G.M. Landau and U. Vishkin.
Efficient string matching with k mismatches.
Theoretical Computer Science 43 (1986), 239249.

R. Cole and U. Vishkin.
Deterministic coin tossing with applications to optimal parallel list
ranking.
Information and Control 70 (1986), 3253.

U. Vishkin.
An optimal parallel algorithm for selection.
Advances in Computing Research 4 (Special Issue on Parallel and
Distributed Computing) (1987), 7986.

Y. Maon, B. Schieber and U. Vishkin.
Parallel ear decomposition search (EDS) and stnumbering in graphs.
Theoretical Computer Science 47 (1986), 277298.

Y. Azar and U. Vishkin.
Tight comparison bounds on the complexity of parallel sorting.
SIAM J. Computing 16,3 (1987), 458464.

U. Vishkin.
Randomized parallel speedups for list ranking.
J. of Parallel and Distributed Computing 4,3 (1987), 319333.

G.M. Landau, U. Vishkin and R. Nussinov.
An efficient string matching algorithm with k substitutions for
nucleotides and amino acid sequences.
J. of Theoretical Biology 126 (1987), 483490.

G.M Landau, U. Vishkin and R. Nussinov.
Locating alignments with k differences for
nucleotide and amino acid sequences.
Computer Applications in the Biosciences (CABIOS) 4,1 (1988), 1924.
Joint issue with Nucleic Acids Research.

R. Cole and U. Vishkin.
The accelerated centroid decomposition technique for optimal
parallel tree evaluation in logarithmic time.
Algorithmica 3 (1988), 329346,
special issue on Parallel and Distributed Computing.

A. Apostolico, C. Iliopoulos, G.M. Landau, B. Schieber and U. Vishkin.
Parallel construction of a suffix tree with applications.
Algorithmica 3 (1988), 347365,
special issue on Parallel and Distributed Computing.

R. Cole and U. Vishkin.
Approximate parallel scheduling. Part I: The basic technique with
applications to optimal parallel list ranking in logarithmic time.
SIAM J. Computing 17 (1988), 128142.

G.M. Landau and U. Vishkin.
Fast string matching with k differences.
J. of Computer Systems and Sciences (special issue of selected
papers from FOCS 1985) 37,1 (1988), 6378.

B. Schieber and U. Vishkin.
On finding lowest common ancestors: simplification and parallelization.
SIAM J. Computing 17,6 (1988), 12531262.

N. Megiddo and U. Vishkin.
On finding a minimum dominating set in a tournament.
Theoretical Computer Science 61, 23 (1988), 307316.

T. TzoreffEilam and U. Vishkin.
Matching patterns in strings subject to multilinear transformations.
Theoretical Computer Science 60 (Special volume on Fundamental Studies),3
(1988), 231254.

G.M. Landau and U. Vishkin.
Fast parallel and serial approximate string matching.
J. of Algorithms 10 (1989), 157169.

R. Cole and U. Vishkin.
Faster optimal prefix sums and list ranking.
Information and Computation 81 (1989), 334352.

G.M. Landau, U. Vishkin and R. Nussinov.
Fast alignment of DNA and protein sequences.
Methods in Enzymology (a volume on Molecular Evolution:
Computer Analysis of Protein and Nucleic Acid Sequences)
183, 1990, 487502.

B. Schieber and U. Vishkin.
Finding all nearest neighbors for convex polygons in parallel:
a new lower bound technique and a matching algorithm.
Discrete Applied Mathematics (Special Issue on Parallel Complexity
Using Combinatorics), 29 (1990), 97111.

U. Vishkin.
Deterministic sampling  a new technique for fast pattern matching.
SIAM J. Computing, 20,1 (1991), 2240.

R. Cole and U. Vishkin.
Approximate parallel scheduling. II. Applications to optimal
parallel graph algorithms in logarithmic time.
Information and Computation 91,1 (1991), 147.

Y. Matias and U. Vishkin.
On parallel hashing and integer sorting.
J. of Algorithms 12,4 (1991) 573606.

A. Amir, G.M. Landau and U. Vishkin.
Efficient pattern matching with scaling.
J. of Algorithms (Special Issue of Papers Selected from 1st ACMSIAM
Symp. on Discrete Algorithms) 13,1 (1992) 232.

U. Vishkin.
A parallel blocking flow algorithm for acyclic networks.
J. of Algorithms 13,3 (1992) 489501.

O. Berkman and U. Vishkin.
Recursive startree parallel datastructure.
SIAM J. Computing 22,2 (1993) 221242.

O. Berkman, B. Schieber and U. Vishkin.
Optimal doubly logarithmic optimal parallel algorithms based on finding
all nearest smaller values.
J. of Algorithms 14 (1993) 344370.

O. Berkman, Y. Matias and U. Vishkin.
Randomized RangeMaxima in NearlyConstant Parallel Time.
Computational Complexity 2 (1992) 350373.

O. Berkman and U. Vishkin.
On parallel integer merging.
Information and Computation 106 (1993), 266285.

S. Khuller and U. Vishkin.
Biconnectivity approximations and graph carvings.
JACM 41,2 (1994), 214235.

O. Berkman, J. JaJa, S. Krishnamurthy, R. Thurimella and U. Vishkin.
Topbottom routing around a rectangle is as easy as computing
prefix minima.
SIAM J. Computing 23,3 (1994), 449465.

O. Berkman and U. Vishkin.
Finding levelancestors in trees.
J. of Computer Systems and Sciences 48,2 (1994), 214230.

R. Cole and U. Vishkin.
On the detection of robust curves.
Computer Vision, Graphics, and Image Processing (CVGIP): Graphical
Models and Image Processing 56,3 (1994), 189204.

G.M. Landau and U. Vishkin.
Pattern matching in a digitized image.
Algorithmica, 12,4/5 (1994), 375408.

S. Khuller, U. Vishkin and N. Young.
A primaldual parallel approximation technique applied to
weighted set and vertex cover.
J. Algorithms, 17,2 (1994), 280289.

S. Khuller and U. Vishkin.
On the parallel complexity of digraph reachability.
Information Processing Letters, 52,5 (1994), 239242.

O. Berkman and U. Vishkin.
Almost fullyparallel parentheses matching.
Discrete Applied Mathematics, 57 (1995), 1128.

J. JaJa, K.W. Ryu, and U. Vishkin.
Sorting strings and constructing search trees in parallel.
Theoretical Computer Science, 154,2 (1996), 225245.

O. Berkman, B. Schieber and U. Vishkin.
A fast parallel algorithm for finding the convex hull of a sorted
point set.
International Journal of Computational Geometry and
Applications, 6 (1996), 231241.

U. Vishkin.
Can parallel algorithms enhance serial implementation?
Communications of the ACM, 39,9 (1996), 8891.
Please see the Explicit MultiThreading (XMT) home page for more recent papers.
BOOK CHAPTERS

U. Vishkin.
Advanced Parallel Prefixsums, List Ranking and Connectivity.
In
Synthesis of Parallel Algorithms (Editor: John H. Reif), MorganKaufmann,
1993, 215258.

U. Vishkin.
Structural parallel algorithmics.
In
Lectures on Parallel Computation,
Editors: Alan Gibbons and Paul Spirakis, Cambridge University Press, 1993, 118.

G.M. Landau and U. Vishkin.
Approximate string matching.
In Pattern Matching Algorithms,
Editors: Alberto Apostolico and Zvi Galil, Oxford University Press, 1997,
185199.
BOOK
 U. Vishkin (editor), Developing a Computer Science Agenda for
HighPerformance Computing, ACM Press, 1994, 158 pages.
ARTICLES IN PROCEEDINGS OF CONFERENCES

Y. Shiloach and U. Vishkin.
Finding the maximum, merging and
sorting in a parallel computation model.
In
Proc. Conference of Analyzing Problem Classes
and Programming for Parallel Computing, CONPAR 81, Nurnberg, F.R.
Germany, Lecture Notes in Computer Science, Vol. 111, Springer
verlag, 1981, 314327.

A.K. Chandra, L.J. Stockmeyer and U. Vishkin.
A complexity theory for unbounded fanin parallelism.
In
Proc. 23rd Annual IEEE
Symposium on Foundations of Computer Science, 1982, 113.

W. Paul, U. Vishkin and H. Wagener.
Parallel dictionaries on 23 trees.
In
Proc. 10th ICALP, Lecture Notes in
Computer Science, Vol. 154, SpringerVerlag, 1983, 597609.

U. Vishkin and A. Wigderson.
Tradeoffs between depth and width in parallel computation.
In
Proc. 24th Annual IEEE Symposium on Foundations of Computer Science,
1983, 146153.

U. Vishkin.
Randomized speedups in parallel computation.
In
Proc. 16th Annual ACM Symp. on Theory of Computing, 1984, 230239.

I. BarOn and U. Vishkin.
Optimal parallel generation of a computation tree form.
In
Proc. 13th Annual International Conference on Parallel
Processing, 1984, 490495.

K. Mehlhorn and U. Vishkin.
Granularity of memory in parallel computation.
In
Proc. 9th Workshop on Graphtheoretic Concepts in Computer Science
(WG83), Fachbereich Mathematik, Universitat Osnabruck, June 1983.

R.E. Tarjan and U. Vishkin.
Finding biconnected components and
computing tree functions in logarithmic parallel time.
In
Proc. 25th
Annual IEEE Symposium on Foundations of Computer Science, 1984, 1220.

U. Vishkin.
Optimal parallel pattern matching in strings.
In
Proc. 12th ICALP, Lecture Note in Computer Science, Vol. 194,
SpringerVerlag, 1985, 497508.

G.M Landau and U. Vishkin.
Efficient string matching in the presence of errors.
In
Proc. 26th
Annual IEEE Symposium on Foundations of Computer Science, 1985, 126136.

R. Cole and U. Vishkin.
Deterministic coin tossing and accelerating cascades: micro and macro
techniques for designing parallel algorithms.
In
Proc.
18th Annual ACM Symp. on Theory of Computing, 1986, 206219.

G.M. Landau and U. Vishkin.
Introducing efficient parallelism into approximate string matching
and a new serial algorithm.
In
Proc. 18th Annual ACM Symp. on Theory of Computing, 1986, 220230.

R. Cole and U. Vishkin.
Approximate and exact parallel scheduling with applications for
list, tree and graph algorithms.
In
Proc. 27th Annual IEEE Symposium on Foundations of Computer
Science, 1986, 478491.

N. Alon, Y. Azar and U. Vishkin.
Tight complexity bounds for parallel comparison sorting.
In
Proc. 27th Annual IEEE Symposium on Foundations of Computer
Science, 1986, 502510.

Y. Maon, B. Schieber and U. Vishkin.
Parallel ear decomposition search (EDS) and stnumbering in graphs.
In
AWOC 86: Proc. 2nd International Workshop on Parallel Computing and
VLSI,
Lecture Notes in Computer Science, Vol. 227,
SpringerVerlag, 1986, 3445.

G.M. Landau, B. Schieber and U. Vishkin.
Parallel construction of a suffix tree.
In
Proc. 14th ICALP, Lecture Notes in Computer Science, Vol. 267
SpringerVerlag, 1987, 314325.

V.L. Ramachandran and U. Vishkin.
Efficient parallel triconnectivity in logarithmic parallel time.
In
AWOC 88: Third International Workshop
on Parallel Computation and VLSI Theory, Corfu
Island, Greece, June 28  July 1, 1988.
Lecture Notes in Computer Science, Vol. 319, SpringerVerlag, 3342.

B. Schieber and U. Vishkin.
On finding lowest common ancestors: simplification and parallelization.
In
AWOC 88: Third International Workshop
on Parallel Computation and VLSI Theory, Corfu
Island, Greece, June 28  July 1, 1988.
Lecture Notes in Computer Science, Vol. 319, SpringerVerlag, 111123.

R. Cole and U. Vishkin.
Optimal parallel algorithms for expression tree evaluation and
list ranking.
In
AWOC 88: Third International Workshop
on Parallel Computation and VLSI Theory, Corfu
Island, Greece, June 28  July 1, 1988.
Lecture Notes in Computer Science, Vol. 319, SpringerVerlag, 91100.

T. TzoreffEilam and U. Vishkin.
Matching patterns in strings subject to multilinear transformations
In
Sequences: Combinatorics, Compression, Security and Transmission,
(ed. R.M. Capocelli), Springerverlag, 1990, 4558.
Workshop was held in Amalfi Coast, Salerno, Italy, on June 610, 1988.

O. Berkman, D. Breslauer, Z. Galil, B. Schieber and U. Vishkin.
Highly parallelizable problems.
In
Proc. 21st Annual ACM Symp. on Theory of Computing, 1989, 309319.

O. Berkman and U. Vishkin.
Recursive *tree parallel datastructure.
In
Proc. 30th Annual IEEE Symposium on Foundations of Computer
Science, 1989, 196202.

A. Amir, G.M. Landau and U. Vishkin.
Efficient pattern matching with scaling.
In
Proc. First Annual ACMSIAM Symp. on Discrete Algorithms,
1990, 344357.

U. Vishkin.
Deterministic sampling  a new technique for fast pattern matching.
In
Proc. 22nd Annual ACM Symp. on Theory of Computing, 1990, 170180.

Y. Matias and U. Vishkin.
On integer sorting and parallel hashing.
In
Proc. 17th ICALP, Lecture Notes in Computer Science, Vol. 443,
SpringerVerlag, 1990, 729743.

O. Berkman, J. JaJa, S. Krishnamurthy, R. Thurimella and U. Vishkin.
Some triplylogarithmic parallel algorithms.
In
Proc. 31st Annual IEEE Symposium on Foundations of Computer
Science, 1990, 871881.

Y. Matias and U. Vishkin.
Converting high probability into nearlyconstant time 
with applications to parallel hashing.
In
Proc. 23rd Annual ACM Symp. on Theory of Computing, 1991, 307316.

U. Vishkin.
Structural parallel algorithmics.
In
Proc. 18th ICALP, Lecture Notes in Computer Science, Vol. 510
SpringerVerlag, 1991, 363380.

J. Gil, Y. Matias and U. Vishkin.
Towards a theory of nearly constant time parallel algorithms.
In
Proc. 32nd Annual IEEE Symposium on Foundations of Computer
Science, 1991, 698710.

G.M. Landau and U. Vishkin.
Pattern matching in a digitized image.
In
Proc. Third Annual ACMSIAM Symp. on Discrete Algorithms, 1992, 453462.

S. Khuller and U. Vishkin.
Biconnectivity approximations and graph carvings.
In
Proc. 24th Annual ACM Symp. on Theory of Computing, 1992, 759770.

U. Vishkin.
Methods in parallel algorithmics and who may need to know them?
In
Proc. Third annual International Symposium on Algorithms and
Computation (ISAAC'92), Lecture Notes in Computer Science,
SpringerVerlag, Vol. 650, 1992, 14.

O. Berkman, Y. Matias and U. Vishkin.
Randomized RangeMaxima in NearlyConstant Parallel Time.
In
Proc. Third annual International Symposium on Algorithms and
Computation (ISAAC'92), Lecture Notes in Computer Science, Vol. 650,
SpringerVerlag, 1992, 135144.

U. Vishkin.
A case for the PRAM as a standard programmer's model.
In
Proc. Workshop on Parallel Architectures and Their Efficient Use:
State of the Art and Perspectives, First HeinzNixdorf Symposium,
Paderborn, Germany, November 11  13, 1992, Lecture Notes in Computer
Science, Volume 678, 1993, 1119.

S. Khuller, U. Vishkin and N. Young.
A primaldual parallel approximation technique applied to
weighted set and vertex cover.
In
Proc. 3rd Integer Programming and Combinatorial Optimization (IPCO)
Conference, 1993, 333341.

G.M. Landau and U. Vishkin.
Two dimensional pattern matching in a digitized image.
In
Proc. Fourth Conference on Combinatorial Pattern Matching,
Lecture Notes in Computer Science, Vol. 684,
SpringerVerlag, 1993, 134151.

M.T. Goodrich, Y. Matias and U. Vishkin.
Approximate parallel prefix computation and its Applications.
In
Proc. 7th IEEE International Parallel Processing Symposium (IPPS), 1993,
318325.

R. Raman and U. Vishkin.
Optimal parallel algorithms for totally monotone matrix searching.
In
Proc. Fifth Annual ACMSIAM Symp. on Discrete Algorithms, 1994, 613621.

M.T. Goodrich, Y. Matias and U. Vishkin.
Optimal parallel approximation algorithms for prefix sums and integer sorting.
In
Proc. Fifth Annual ACMSIAM Symp. on Discrete Algorithms, 1994, 241250.

J. JaJa, K.W. Ryu, and U. Vishkin.
Sorting strings and constructing search trees in parallel.
In
Proc. 8th IEEE International Parallel Processing Symposium (IPPS), 1994,
349356.

U. Vishkin.
Can parallel algorithms enhance serial implementation?
In
Proc. 8th IEEE International Parallel Processing Symposium (IPPS), 1994,
376385.

S. C. Sahinalp and U. Vishkin.
Symmetry breaking for suffix tree construction.
In
Proc. 26th Annual ACM Symp. on Theory of Computing, 1994, 300309.

Y. Mansour, N. Nisan, and U. Vishkin.
Tradeoffs between communication throughput and parallel time.
In Proc. 26th Annual ACM Symp. on Theory of Computing, 1994,
372381.

S. C. Sahinalp and U. Vishkin.
On a parallelalgorithms method for string matching problems.
In
The second Italian Conference on Algorithms and Complexity, Rome, Italy,
Lecture Notes in Computer Science, Vol. 778, Springerverlag, 1994, 2232.

Y. Matias and U. Vishkin.
A note on reducing parallel model simulations to integer sorting.
In
Proc. 9th IEEE International Parallel Processing Symposium (IPPS), 1995.

R. Raman and U. Vishkin.
Parallel algorithms for database operations and a
database operation for parallel algorithms.
In
Proc. 9th IEEE International Parallel Processing Symposium (IPPS), 1995.

S. C. Sahinalp and U. Vishkin.
Efficient approximate and dynamic matching of patterns using a
labeling paradigm.
In Proc. 37th Annual IEEE Symposium on Foundations of Computer
Science, 1996.

S.M. Mueller and U. Vishkin.
ConflictFree Access to Multiple SinglePorted Register Files.
In
Proc. 11th IEEE International Parallel Processing Symposium (IPPS), 1997.

U. Vishkin.
From algorithm parallelism to instructionlevel parallelism:
an encodedecode chain using prefixsum.
In Proc. 9th ACM Symposium on Parallel Algorithms and
Architectures (SPAA), 1997.

U. Vishkin, S. Dascal, E. Berkovich and J. Nuzman.
Explicit MultiThreading (XMT) Bridging Models for Instruction Parallelism.
In Proc. 10th ACM Symposium on Parallel Algorithms and
Architectures (SPAA), 1998.
Please see the Explicit MultiThreading (XMT) home page for more recent papers.
THESES

U. Vishkin.
Information in Economics.
M.Sc. Thesis, Department of Mathematics, Hebrew University, Jerusalem,
Israel, 1975. Advisor: Prof. R.J. Aumann.

U. Vishkin.
Synchronized Parallel Computation.
D.Sc. Thesis, Computer Science Department, Technion, Haifa, Israel,
1981.
Main results appear in journal articles 1,2 and 6.
Advisor: Prof. Y. Shiloach.
OTHER ARTICLES

U. Vishkin.
Synchronous parallel computation  a survey.
TR 71, Department of Computer Science, Courant Institute, New York
University, 1983. The paper also appeared (by their invitation) at the
annual paper collection of "Datalogforeningen" (The Computer Science
Association of Aarhus, Denmark), 1987, 7689.
The theme of the 1987 volume
is "parallelism" and it included eleven papers.

U. Vishkin.
On choice of a parallel model of computation.
TR61, Dept. of Computer Science, Courant Institute, New York
University, 1983.

U. Vishkin.
Project for developing computer science agenda(s) for highperformance
computing: an organizer's summary.
UMIACSTR94129, University of Maryland Institute for Advanced Computer
Studies, College Park, MD 207423251, November 1994.

R. Orny and U. Vishkin.
Two computer systems paradoxes: serializetoparallelize, and queuing
concurrentwrites,
UMIACSTR961, University of Maryland Institute for Advanced Computer
Studies, College Park, MD 207423251, September 1995.
Fri Jan 3 12:12:11 EST 1997