Shimon Even, Gene Itkis, Sergio Rajsbaum (auth.), Paul Spirakis (eds.)3540603131, 9783540603139
The volume presents 42 full revised papers selected during a careful refereeing process from a total of 119 submissions; in addition, there is a prominent keynote address. This year, the scope has been further expanded to new areas of computational endeavour in science; the book covers many aspects of algorithms research and application ranging from combinatorial mathematics to hardware design.
Table of contents :
On mixed connectivity certificates….Pages 1-16
Truly efficient parallel algorithms: c-optimal multisearch for an extension of the BSP model….Pages 17-30
Optimal parallel shortest paths in small treewidth digraphs….Pages 31-45
Shared memory simulations with triple-logarithmic delay….Pages 46-59
Implementing shared memory on multi-dimensional meshes and on the fat-tree….Pages 60-74
Beyond the worst-case bisection bound: Fast sorting and ranking on meshes….Pages 75-88
Fast deterministic simulation of computations on faulty parallel machines….Pages 89-101
Average circuit depth and average communication complexity….Pages 102-112
Packing trees….Pages 113-127
Sometimes travelling is easy: The master tour problem….Pages 128-141
Interval graphs with side (and size) constraints….Pages 142-154
Maximum skew-symmetric flows….Pages 155-170
Certificates and fast algorithms for biconnectivity in fully-dynamic graphs….Pages 171-184
On the all-pairs shortest path algorithm of Moffat and Takaoka….Pages 185-198
Fully Dynamic Transitive Closure in plane dags with one source and one sink….Pages 199-212
Planarity for clustered graphs….Pages 213-226
A geometric approach to betweenness….Pages 227-237
Efficient computation of the geodesic Voronoi diagram of points in a simple polygon….Pages 238-251
Linear size binary space partitions for fat objects….Pages 252-263
Geometric pattern matching in d -dimensional space….Pages 264-279
Finding the constrained Delaunay triangulation and constrained Voronoi diagram of a simple polygon in linear-time….Pages 280-294
External-memory algorithms for processing line segments in geographic information systems….Pages 295-310
Optimized binary search and text retrieval….Pages 311-326
On using q -gram locations in approximate string matching….Pages 327-340
Routing with bounded buffers and hot-potato routing in vertex-symmetric networks….Pages 341-354
Load balancing for response time….Pages 355-368
Self-simulation for the Passive Optical Star model….Pages 369-380
Computing the agreement of trees with bounded degrees….Pages 381-393
Approximation algorithms for feasible cut and multicut problems….Pages 394-408
On parallel versus sequential approximation….Pages 409-419
An efficient and effective approximation algorithm for the Map Labeling Problem….Pages 420-433
Approximating the bandwidth for asteroidal triple-free graphs….Pages 434-447
Near-optimal distributed edge coloring….Pages 448-459
The centroid of points with approximate weights….Pages 460-472
0/1-Integer programming: Optimization and Augmentation are equivalent….Pages 473-483
The online transportation problem….Pages 484-493
A polyhedral approach to planar augmentation and related problems….Pages 494-507
Optimal layouts on a chain ATM network….Pages 508-522
Efficient Dynamic-Resharing “Verifiable Secret Sharing” against mobile adversary….Pages 523-537
Adaptive Video on Demand….Pages 538-553
The binomial transform and its application to the analysis of skip lists….Pages 554-569
An optimal parallel algorithm for digital curve segmentation using hough polygons and monotone function search….Pages 570-581
Fast skeleton construction….Pages 582-595
Reviews
There are no reviews yet.