Algorithms - ESA '94 Book

	Optimization Algorithms for Large Networks	1
	Wanna Buy an Algorithm? Cheap! or: Algorithms for Text Searching Which Could Have Commercial Value	10
	Planar Drawings and Angular Resolution: Algorithms and Bounds	12
	A Better Heuristic for Orthogonal Graph Drawings	24
	Hamiltonian Triangulations for Fast Rendering	36
	Efficient Construction of a Bounded Degree Spanner with Low Weight	48
	Approaching the 5/4-Approximation for Rectilinear Steiner Trees	60
	Membership in Constant Time and Minimum Space	72
	Faster Searching in Tries and Quadtrees - An Analysis of Level Compression	82
	The Analysis of a Hashing Scheme by the Diagonal Poisson Transform	94
	Some Lower Bounds for Comparison-Based Algorithms	106
	An Efficient Algorithm for Edge-Ranking Trees	118
	Edge-Disjoint (s,t)-Paths in Undirected Planar Graphs in Linear Time	130
	A Simple Min Cut Algorithm	141
	Approximation Algorithm on Multi-Way Maxcut Partitioning	148
	A Linear-Time Algorithm for Finding a Central Vertex of a Chordal Graph	159
	The Time Complexity of Updating Snapshot Memories	171
	Non-Exploratory Self-Stabilization for Constant-Space Symmetry-Breaking	183
	On-Line Distributed Data Management	202
	A Unified Scheme for Detecting Fundamental Curves in Binary Edge Images	215
	How to Compute the Voronoi Diagram of Line Segments: Theoretical and Practical Results	227
	Range Searching and Point Location among Fat Objects	240
	Convex Tours of Bounded Curvature	254
	Optimal Shortest Path and Minimum-Link Path Queries in the Presence of Obstacles	266
	Fast Algorithms for Collision and Proximity Problems Involving Moving Geometric Objects	278
	Reverse-Fit: A 2-Optimal Algorithm for Packing Rectangles	290
	An Optimal Algorithm for Preemptive On-Line Scheduling	300
	Tight Approximations for Resource Constrained Scheduling Problems	307
	An Algorithm for 0-1 Programming with Application to Airline Crew Scheduling	319
	An o(n) Work EREW Parallel Algorithm for Updating MST	331
	On the Structure of DFS-Forests on Directed Graphs and the Dynamic Maintenance of DFS on DAG's	343
	Finding and Counting Given Length Cycles	354
	Greedy Hot-Potato Routing on the Mesh	365
	Desnakification of Mesh Sorting Algorithms	377
	Tight Bounds on Deterministic PRAM Emulations with Constant Redundancy	391
	PRAM Computations Resilient to Memory Faults	401
	An Area Lower Bound for a Class of Fat-Trees	413
	A Unified Approach to Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs	424
	The Parallel Complexity of Eden Growth, Solid-on-Solid Growth and Ballistic Deposition	436
	A New Approach to Resultant Computations and Other Algorithms with Exact Division	448
	Testing Equivalence of Morphisms on Context-Free Languages	460
	Work-Time Optimal Parallel Prefix Matching	471
	On the Exact Complexity of the String Prefix-Matching Problem	483
	Incremental Text Editing: A New Data Structure	495
	Erratum to the ESA '93 Proceedings	508
	Authors Index	509