Algorithm theory -- SWAT '96. 5th Scandinavian workshop on algorithm theory, Reykjavík, Iceland, July 3--5, 1996. Proceedings (Q1919222)

The articles of this volume will be reviewed individually. For the preceding workshop see [Zbl 0816.00031]. Indexed articles: \textit{Brodal, Gerth Stølting; Chaudhuri, Shiva; Radhakrishnan, Jaikumar}, The randomized complexity of maintaining the minimum, 4-15 [Zbl 1502.68137] \textit{Henzinger, Monika Rauch; Telle, Jan Arne}, Faster algorithms for the nonemptiness of Streett automata and for communication protocol pruning, 16-27 [Zbl 1502.68383] \textit{Marathe, Madhav V.; Ravi, R.; Sundaram, R.}, Service-constrained network design problems, 28-40 [Zbl 1502.68240] \textit{Kelsen, Pierre; Mahajan, Sanjeev; Ramesh, Hariharan}, Approximate hypergraph coloring, 41-52 [Zbl 0886.05091] \textit{Chandra, Barun; Halldórsson, Magnús M.}, Facility dispersion and remote subgraphs, 53-65 [Zbl 1502.68216] \textit{Ravi, R.; Goemans, M. X.}, The constrained minimum spanning tree problem (extended abstract), 66-75 [Zbl 1502.90184] \textit{Lau, Hoong Chuin; Watanabe, Osamu}, Randomized approximation of the constraint satisfaction problem, 76-87 [Zbl 0889.90116] \textit{Klauck, Hartmut}, On the hardness of global and local approximation, 88-99 [Zbl 0890.68073] \textit{Asano, Takao; Ono, Takao; Hirata, Tomio}, Approximation algorithms for the maximum satisfiability problem, 100-111 [Zbl 0886.03033] \textit{Hirata, Kouichi; Shimozono, Shinichi; Shinohara, Ayumi}, On the hardness of approximating the minimum consistent OBDD problem, 112-123 [Zbl 1502.68133] \textit{Lam, T. W.; Sung, W. K.; Ting, H. F.}, Computing the unrooted maximum agreement subtree in sub-quadratic time, 124-135 [Zbl 1504.68279] \textit{Asahiro, Yuichi; Iwama, Kazuo; Tamaki, Hisao; Tokuyama, Takeshi}, Greedily finding a dense subgraph, 136-148 [Zbl 1502.68201] \textit{Fernández-Baca, David; Slutzki, Giora; Eppstein, David}, Using sparsification for parametric minimum spanning tree problems, 149-160 [Zbl 1502.68224] \textit{Gupta, Arvind; Kaller, Damon; Mahajan, Sanjeev; Shermer, Tom}, Vertex partitioning problems on partial \(k\)-trees, 161-172 [Zbl 0886.05106] \textit{Blair, Jean R. S.; Heggernes, Pinar; Telle, Jan Arne}, Making an arbitrary filled graph minimal by removing fill edges, 173-184 [Zbl 0886.05104] \textit{Andersson, Arne}, Sorting and searching revisted, 185-197 [Zbl 1502.68106] \textit{Husfeldt, Thore; Rauhe, Theis; Skyum, Søren}, Lower bounds for dynamic transitive closure, planar point location, and parentheses matching, 198-211 [Zbl 1502.68134] \textit{Alstrup, Stephen; Thorup, Mikkel}, Optimal pointer algorithms for finding nearest common ancestors in dynamic trees, 212-222 [Zbl 1504.68277] \textit{Kelsen, Pierre}, Neighborhood graphs and distributed \(\Delta +1\)-coloring, 223-233 [Zbl 1502.68235] \textit{Gargano, Luisa; Rescigno, Adele A.; Vaccaro, Ugo}, Communication complexity of gossiping by packets, 234-245 [Zbl 1502.68037] \textit{Przytycka, Teresa; Higham, Lisa}, Optimal cost-sensitive distributed minimum spanning tree algorithm, 246-258 [Zbl 1502.68245] \textit{Auletta, Vincenzo; Monti, Angelo; Parente, Mimmo; Persiano, Pino}, A linear time algorithm for the feasibility of pebble motion on trees, 259-270 [Zbl 1502.68196] \textit{Levcopoulos, Christos; Östlin, Anna}, Linear-time heuristics for minimum weight rectangulation (extended abstract), 271-283 [Zbl 1502.68334] \textit{Aronov, Boris; Davis, Alan R.; Dey, Tamal K.; Pal, Sudebkumar P.; Prasad, D. Chithra}, Visibility with multiple reflections, 284-295 [Zbl 1502.68298] \textit{Levcopoulos, Christos; Krznaric, Drago}, A fast heuristic for approximating the minimum weight triangulation (extended abstract), 296-308 [Zbl 1502.68332] \textit{Brodnik, Andrej; Munro, J. Ian}, Neighbours on a grid, 309-320 [Zbl 1502.68089] \textit{Azar, Yossi; Epstein, Leah}, On two dimensional packing, 321-332 [Zbl 1502.90140] \textit{Biedl, Therese C.}, Optimal orthogonal drawings of triconnected plane graphs, 333-344 [Zbl 1502.68209] \textit{López-Ortiz, Alejandro; Schuierer, Sven}, Walking streets faster, 345-356 [Zbl 1502.68336] \textit{Preminger, Sonne; Upfal, Eli}, Safe and efficient traffic laws for mobile robots, 357-367 [Zbl 1502.68291] \textit{Paterson, Mike}, Progress in selection, 368-379 [Zbl 1502.68111] \textit{Gonnet, Gaston H.; Benner, Steven A.}, Probabilistic ancestral sequences and multiple alignments, 380-391 [Zbl 1502.68380] \textit{Gasieniec, Leszek; Karpinski, Marek; Plandowski, Wojciech; Rytter, Wojciech}, Efficient algorithms for Lempel-Ziv encoding (extended abstract), 392-403 [Zbl 1502.68379] \textit{Bäumker, Armin; Dittrich, Wolfgang; Pietracaprina, Andrea}, The deterministic complexity of parallel multisearch (extended abstract), 404-415 [Zbl 1502.68107] \textit{Brodal, Gerth Stølting}, Priority queues on parallel machines, 416-427 [Zbl 1502.68046] \textit{Fagerberg, Rolf}, Binary search trees: how low can you go?, 428-439 [Zbl 1502.68097] \textit{Boros, Endre; Ibaraki, Toshihide; Makino, Kazuhisa}, Boolean analysis of incomplete examples, 440-451 [Zbl 1502.68141]