Algorithms - ESA '94

Optimization algorithms for large networks.- Wanna buy an algorithm? Cheap! or: Algorithms for text searching which could have commercial value.- Planar drawings and angular resolution: Algorithms and bounds.- A better heuristic for orthogonal graph drawings.- Hamiltonian triangulations for fast rendering.- Efficient construction of a bounded degree spanner with low weight.- Approaching the 5/4 — approximation for rectilinear Steiner trees.- Membership in constant time and minimum space.- Faster searching in tries and quadtrees—An analysis of level compression.- The analysis of a hashing scheme by the diagonal poisson transform.- Some lower bounds for comparison-based algorithms.- An efficient algorithm for edge-ranking trees.- Edge-disjoint (s, t)-paths in undirected planar graphs in linear time.- A simple min cut algorithm.- Approximation algorithm on multi-way maxcut partitioning.- A linear-time algorithm for finding a central vertex of a chordal graph.- The time complexity of updating snapshot memories.- Non-exploratory self-stabilization for constant-space symmetry-breaking.- On-line distributed data management.- A unified scheme for detecting fundamental curves in binary edge images.- How to compute the Voronoi diagram of line segments: Theoretical and experimental results.- Range searching and point location among fat objects.- Convex tours of bounded curvature.- Optimal shortest path and minimum-link path queries in the presence of obstacles.- Fast algorithms for collision and proximity problems involving moving geometric objects.- Reverse-Fit: A 2-optimal algorithm for packing rectangles.- An optimal algorithm for preemptive on-line scheduling.- Tight approximations for resource constrained scheduling problems.- An algorithm for 0–1 programming with application to airline crew scheduling.- An o(n) work EREW parallel algorithm for updating MST.- On the structure of DFS-forests on directed graphs and the dynamic maintenance of DFS on DAG's.- Finding and counting given length cycles.- Greedy hot-potato routing on the mesh.- Desnakification of mesh sorting algorithms.- Tight bounds on deterministic PRAM emulations with constant redundancy.- PRAM computations resilient to memory faults.- An area lower bound for a class of fat-trees.- A unified approach to approximation schemes for NP- and PSPACE-hard problems for geometric graphs.- The parallel complexity of eden growth, solid-on-solid growth and ballistic deposition.- A new approach to resultant computations and other algorithms with exact division.- Testing equivalence of morphisms on context-free languages.- Work-time optimal parallel prefix matching.- On the exact complexity of the string prefix-matching problem.- Incremental text editing: a new data structure.- The ESA '93 Proceedings.