Algorithms - ESA '95

On mixed connectivity certificates.- Truly efficient parallel algorithms: c-optimal multisearch for an extension of the BSP model.- Optimal parallel shortest paths in small treewidth digraphs.- Shared memory simulations with triple-logarithmic delay.- Implementing shared memory on multi-dimensional meshes and on the fat-tree.- Beyond the worst-case bisection bound: Fast sorting and ranking on meshes.- Fast deterministic simulation of computations on faulty parallel machines.- Average circuit depth and average communication complexity.- Packing trees.- Sometimes travelling is easy: The master tour problem.- Interval graphs with side (and size) constraints.- Maximum skew-symmetric flows.- Certificates and fast algorithms for biconnectivity in fully-dynamic graphs.- On the all-pairs shortest path algorithm of Moffat and Takaoka.- Fully Dynamic Transitive Closure in plane dags with one source and one sink.- Planarity for clustered graphs.- A geometric approach to betweenness.- Efficient computation of the geodesic Voronoi diagram of points in a simple polygon.- Linear size binary space partitions for fat objects.- Geometric pattern matching in d-dimensional space.- Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time.- External-memory algorithms for processing line segments in geographic information systems.- Optimized binary search and text retrieval.- On using q-gram locations in approximate string matching.- Routing with bounded buffers and hot-potato routing in vertex-symmetric networks.- Load balancing for response time.- Self-simulation for the Passive Optical Star model.- Computing the agreement of trees with bounded degrees.- Approximation algorithms for feasible cut and multicut problems.- On parallel versus sequential approximation.- An efficient and effective approximation algorithm for the Map Labeling Problem.- Approximating the bandwidth for asteroidal triple-free graphs.- Near-optimal distributed edge coloring.- The centroid of points with approximate weights.- 0/1-Integer programming: Optimization and Augmentation are equivalent.- The online transportation problem.- A polyhedral approach to planar augmentation and related problems.- Optimal layouts on a chain ATM network.- Efficient Dynamic-Resharing "Verifiable Secret Sharing" against mobile adversary.- Adaptive Video on Demand.- The binomial transform and its application to the analysis of skip lists.- An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search.- Fast skeleton construction.