Optimal Algorithms

Randomization in parallel algorithms and its impact on computational geometry.- There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees.- Computing digitized voronoi diagrams on a systolic screen and applications to clustering.- PRAM algorithms for identifying polygon similarity.- A framework for parallel graph algorithm design.- Fast soliton automata.- An upper bound on the order of locally testable deterministic finite automata.- A fast algorithm to decide on simple grammars equivalence.- Complexity of the parallel Givens factorization on shared memory architectures.- Optimal bounds on the dictionary problem.- Optimal constant space move-to-fear list organization.- Improved bounds on the size of separators of toroidal graphs.- On some properties of (a,b)-trees.- Disassembling two-dimensional composite parts via translations.- Which triangulations approximate the complete graph?.- The approximability of problems complete for P.- A structural overview of NP optimization problems.- Sorting within distance bound on a mesh-connected processor array.- Local insertion sort revisited.- Packet routing on grids of processors.- Optimal parallel computations for halin graphs.- Optimal parallel algorithms for b-matchings in trees.