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

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