Algorithm Theory — SWAT’96: 5th Scandinavian Workshop on Algorithm Theory Reykjavík, Iceland, July 3–5, 1996 Proceedings

Noga Alon (auth.), Rolf Karlsson, Andrzej Lingas (eds.)9783540614227, 3540614222

This book constitutes the refereed proceedings of the Fifth Scandinavian Workshop on Algorithm Theory, SWAT ’96, held in Reykjavik, Iceland, in July 1996.
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