Algorithms - ESA '95 Book

	Key note address
	On Mixed Connectivity Certificates	1
	Truly Efficient Parallel Algorithms : c-Optimal Multisearch for an Extension of the BSP Model	17
	Optimal Parallel Shortest Paths in Small Treewidth Digraphs	31
	Shared Memory Simulations with Triple-Logarithmic Delay	46
	Implementing Shared Memory on Multi-Dimensional Meshes and on the Fat-Tree	60
	Beyond the Worst-Case Bisection Bound: Fast Sorting and Ranking on Meshes	75
	Fast Deterministic Simulation of Computations on Faulty Parallel Machines	89
	Average Circuit Depth and Average Communication Complexity	102
	Packing Trees	113
	Sometimes Travelling is Easy: The Master Tour Problem	128
	Interval Graphs with Side (and Size) Constraints	142
	Maximum Skew-Symmetric Flows	155
	Certificates and Fast Algorithms for Biconnectivity in Fully-Dynamic Graphs	171
	On the All-Pairs Shortest Path Algorithm of Moffat and Takaoka	185
	Fully Dynamic Transitive Closure in Plane Dags with One Source and One Sink	199
	Planarity for Clustered Graphs	213
	A Geometric Approach to Betweenness	227
	Efficient Computation of the Geodesic Voronoi Diagram of Points in a Simple Polygon	238
	Linear Size Binary Space Partitions for Fat Objects	252
	Geometric Pattern Matching in d-Dimensional Space	264
	Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear-Time	280
	External-Memory Algorithms for Processing Line Segments in Geographic Information Systems	295
	Optimized Binary Search and Text Retrieval	311
	On Using q-Gram Locations in Approximate String Matching	327
	Routing with Bounded Buffers and Hot-Potato Routing in Vertex-Symmetric Networks	341
	Load Balancing for Response Time	355
	Self-Simulation for the Passive Optical Star Model	369
	Computing the Agreement of Trees with Bounded Degrees	381
	Approximation Algorithms for Feasible Cut and Multicut Problems	394
	On Parallel versus Sequential Approximation	409
	An Efficient and Effective Approximation Algorithm for the Map Labeling Problem	420
	Approximating the Bandwidth for Asteroidal Triple-free Graphs	434
	Near-Optimal Distributed Edge Coloring	448
	The Centroid of Points with Approximate Weights	460
	0/1-Integer Programming: Optimization and Augmentation are Equivalent	473
	The Online Transportation Problem	484
	A Polyhedral Approach to Planar Augmentation and Related Problems	494
	Optimal Layouts on a Chain ATM Network	508
	Efficient Dynamic-Resharing "Verifiable Secret Sharing" Against Mobile Adversary	523
	Adaptive Video On Demand	538
	The Binomial Transform and its Application to the Analysis of Skip Lists	554
	An Optimal Parallel Algorithm for Digital Curve Segmentation Using Hough Polygons and Monotone Function Search	570
	Fast Skeleton Construction	582
	Author's Index	597