Gianfranco Bilardi, Franco P. Preparata (auth.), Selim G. Akl, Frank Dehne, Jörg-Rüdiger Sack, Nicola Santoro (eds.)3540602208, 9783540602200
The book presents 40 full refereed papers selected from a total of 121 submissions together with invited papers by Preparata and Bilardi, Sharir, Toussaint, and Vitanyi and Li. The book addresses various aspects of algorithms, data structures, computational geometry, scheduling, computational graph theory, and searching.
Table of contents :
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
Reviews
There are no reviews yet.