Algorithms and Data Structures: 4th International Workshop, WADS '95 Kingston, Canada, August 16–18, 1995 Proceedings

Lower bounds to processor-time tradeoffs under bounded-speed message propagation....Pages 1-12
The two-line center problem from a polar view: a new algorithm and data structure....Pages 13-25
On some geometric selection and optimization problems via sorted matrices....Pages 26-37
Load balancing in quorum systems....Pages 38-49
Balanced distributed search trees do not exist....Pages 50-61
Two-floodlight illumination of convex polygons....Pages 62-73
On the complexity of approximating and illuminating three-dimensional convex polyhedra....Pages 74-85
Scheduling jobs that arrive over time....Pages 86-97
Dynamic algorithms for the Dyck languages....Pages 98-108
Arrangements in higher dimensions: Voronoi diagrams, motion planning, and other applications....Pages 109-121
Computing a shortest watchman path in a simple polygon in polynomial-time....Pages 122-134
Going home through an unknown street....Pages 135-146
Page migration with limited local memory capacity....Pages 147-158
Randomized algorithms for metrical task systems....Pages 159-170
Efficient geometric algorithms for workpiece orientation in 4- and 5-axis NC-machining....Pages 171-182
Computing common tangents without a separating line....Pages 183-193
Online perfect matching and mobile computing....Pages 194-205
Competitive algorithms for the on-line traveling salesman....Pages 206-217
Quadrangulations of planar sets....Pages 218-227
A linear-time construction of the relative neighborhood graph within a histogram....Pages 228-238
Computing proximity drawings of trees in the 3-dimensional space....Pages 239-250
Routing on trees via matchings....Pages 251-262
A ranking algorithm for Hamilton paths in shuffle-exchange graphs....Pages 263-269
Amortization results for chromatic search trees, with an application to priority queues....Pages 270-281
Fast meldable priority queues....Pages 282-290
On the computation of fast data transmissions in networks with capacities and delays....Pages 291-302
Routing with delays when storage is costly....Pages 303-314
Algorithmic arguments in physics of computation....Pages 315-333
The buffer tree: A new technique for optimal I/O-algorithms....Pages 334-345
Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep....Pages 346-357
Computing a dominating pair in an asteroidal triple-free graph in linear time....Pages 358-368
A linear algorithm for the maximal planar subgraph problem....Pages 369-380
Topology B-trees and their applications....Pages 381-392
In-place calculation of minimum-redundancy codes....Pages 393-402
Regular-factors in the complements of partial k -trees....Pages 403-414
Obstructions to within a few vertices or edges of acyclic....Pages 415-427
Faster enumeration of all spanning trees of a directed graph....Pages 428-439
A simpler minimum spanning tree verification algorithm....Pages 440-448
On approximation properties of the Independent set problem for degree 3 graphs....Pages 449-460
Approximation of Constraint Satisfaction via local search....Pages 461-472
On the difficulty of range searching....Pages 473-481
Tables should be sorted (on random access machines)....Pages 482-493
Improved length bounds for the shortest superstring problem....Pages 494-505
Nonoverlapping local alignments (weighted independent sets of axis parallel rectangles)....Pages 506-517
Experiences with the implementation of geometric algorithms....Pages 518-518