Noga Alon (auth.), Rolf Karlsson, Andrzej Lingas (eds.)9783540614227, 3540614222
The 35 full papers included in the book in revised version were carefully selected from a total of 95 submissions; also included are abstracts or full versions of three invited talks by prominent researchers. All in all, the collection of articles reports state-of-the-art results on various topics of current design and analysis of algorithms.
Table of contents :
Derandomization via small sample spaces….Pages 1-3
The randomized complexity of maintaining the minimum….Pages 4-15
Faster algorithms for the nonemptiness of streett automata and for communication protocol pruning….Pages 16-27
Service-constrained network design problems….Pages 28-40
Approximate hypergraph coloring….Pages 41-52
Facility dispersion and remote subgraphs….Pages 53-65
The constrained minimum spanning tree problem….Pages 66-75
Randomized approximation of the constraint satisfaction problem….Pages 76-87
On the hardness of global and local approximation….Pages 88-99
Approximation algorithms for the maximum satisfiability problem….Pages 100-111
On the hardness of approximating the minimum consistent OBDD problem….Pages 112-123
Computing the unrooted maximum agreement subtree in sub-quadratic time….Pages 124-135
Greedily finding a dense subgraph….Pages 136-148
Using sparsification for parametric minimum spanning tree problems….Pages 149-160
Vertex partitioning problems on partial k -trees….Pages 161-172
Making an arbitrary filled graph minimal by removing fill edges….Pages 173-184
Sorting and searching revisted….Pages 185-197
Lower bounds for dynamic transitive closure, planar point location, and parentheses matching….Pages 198-211
Optimal pointer algorithms for finding nearest common ancestors in dynamic trees….Pages 212-222
Neighborhood graphs and distributed Δ+1-coloring….Pages 223-233
Communication complexity of gossiping by packets….Pages 234-245
Optimal cost-sensitive distributed minimum spanning tree algorithm….Pages 246-258
A linear time algorithm for the feasibility of pebble motion on trees….Pages 259-270
Linear-time heuristics for minimum weight rectangulation….Pages 271-283
Visibility with multiple reflections….Pages 284-295
A fast heuristic for approximating the minimum weight triangulation….Pages 296-308
Neighbours on a grid….Pages 309-320
On two dimensional packing….Pages 321-332
Optimal orthogonal drawings of triconnected plane graphs….Pages 333-344
Walking streets faster….Pages 345-356
Safe and efficient traffic laws for mobile robots….Pages 357-367
Progress in selection….Pages 368-379
Probabilistic ancestral sequences and multiple alignments….Pages 380-391
Efficient algorithms for Lempel-Ziv encoding….Pages 392-403
The deterministic complexity of parallel multisearch….Pages 404-415
Priority queues on parallel machines….Pages 416-427
Binary search trees: How low can you go?….Pages 428-439
Boolean analysis of incomplete examples….Pages 440-451
Reviews
There are no reviews yet.