SWAT '90. 2nd Scandinavian workshop on algorithm theory, Bergen, Norway, July 11--14, 1990. Proceedings (Q1188841)

The articles of this volume will be reviewed individually. For the preceding workshop see [Zbl 0639.00043]. This volume consists of the papers presented at the Second Scandinavian Workshop on Algorithm Theory held July 11--14, 1990, in Bergen, Norway. They deal with research on algorithms and data structures, mainly in areas such as: combinatorics, computational geometry, parallel computing and graph theory. Indexed articles: \textit{Hartmanis, Juris; Chang, Richard; Ranjan, Desh; Rohatgi, Pankaj}, Structural complexity theory: recent surprises, 1-12 [Zbl 1502.68129] \textit{Boppana, Ravi; Halldórsson, Magnús M.}, Approximating maximum independent sets by excluding subgraphs, 13-25 [Zbl 1502.68212] \textit{Althöfer, Ingo; Das, Gautam; Dobkin, David; Joseph, Deborah}, Generating sparse spanners for weighted graphs, 26-37 [Zbl 1502.68198] \textit{Eppstein, David}, Finding the \(k\) smallest spanning trees, 38-47 [Zbl 1502.68222] \textit{Kant, Goos; van Leeuwen, Jan}, The file distribution problem for processor networks, 48-59 [Zbl 1502.68039] \textit{de Berg, Mark}, Translating polygons with applications to hidden surface removal, 60-70 [Zbl 1502.68311] \textit{Preparata, Franco P.; Vitter, Jeffrey Scott; Yvinec, Mariette}, Output-sensitive generation of the perspective view of isothetic parallelepipeds (extended abstract), 71-84 [Zbl 1502.68340] \textit{Pocchiola, Michel}, Graphics in flatland revisited, 85-96 [Zbl 1502.68339] \textit{Vegter, Gert}, The visibility diagram: a data structure for visibility problems and motion planning, 97-110 [Zbl 1502.68350] \textit{Andersson, Arne; Lai, Tony W.}, Fast updating of well-balanced trees, 111-121 [Zbl 1502.68080] \textit{Ottmann, Thomas; Wood, Derick}, How to update a balanced binary tree with a constant number of rotations, 122-131 [Zbl 1502.68101] \textit{Bent, Samuel W.}, Ranking trees generated by rotations, 132-142 [Zbl 1502.68084] \textit{Baeza-Yates, Ricardo; Gonnet, Gaston H.; Ziviani, Nivio}, Expected behaviour analysis of AVL trees, 143-159 [Zbl 1502.68082] \textit{Papadakis, Thomas; Munro, J. Ian; Poblete, Patricio V.}, Analysis of the expected search cost in skip lists, 160-172 [Zbl 1502.68102] \textit{Dietz, Paul F.; Zhang, Ju}, Lower bounds for monotonic list labeling, 173-180 [Zbl 1502.68096] \textit{Levcopoulos, Christos; Petersson, Ola}, Sorting shuffled monotone sequences, 181-191 [Zbl 1502.68110] \textit{Atallah, Mikhail J.}, A faster parallel algorithm for a matrix searching problem, 192-200 [Zbl 1502.68355] \textit{Richards, Dana S.; Salowe, Jeffrey S.}, A rectilinear Steiner minimal tree algorithm for convex point sets, 201-212 [Zbl 1502.68341] \textit{de Berg, Mark; van Kreveld, Marc; Nilsson, Bengt J.; Overmars, Mark H.}, Finding shortest paths in the presence of orthogonal obstacles using a combined \(L_1\) and link metric, 213-224 [Zbl 1502.68314] \textit{Friedman, Joseph; Hershberger, John; Snoeyink, Jack}, Input-sensitive compliant motion in the plane, 225-237 [Zbl 1504.68254] \textit{Levcopoulos, Christos; Lingas, Andrzej}, Fast algorithms for greedy triangulation, 238-250 [Zbl 1502.68333] \textit{Agarwal, Pankaj K.; Aronov, Boris; O'Rourke, Joseph; Schevon, Catherine A.}, Star unfolding of a polytope with applications (extended abstract), 251-263 [Zbl 1502.68293] \textit{Fernández-Baca, David}, Space-sweep algorithms for parametric optimization (extended abstract), 264-275 [Zbl 1502.90173] \textit{Korneenko, N. M.; Martini, H.}, Approximating finite weighted point sets by hyperplanes, 276-286 [Zbl 1502.68329] \textit{Pantziou, Grammati E.; Spirakis, Paul G.; Zaroliagis, Christos D.}, Efficient parallel algorithms for shortest paths in planar graphs, 288-300 [Zbl 1502.68243] \textit{Bodlaender, Hans L.; Möhring, Rolf H.}, The pathwidth and treewidth of cographs, 301-309 [Zbl 1502.05232] \textit{Arnborg, Stefan; Proskurowski, Andrzej}, Canonical representations of partial 2-and 3-trees, 310-319 [Zbl 1502.68200] \textit{Fernández-Baca, David; Williams, Mark A.}, On matroids and hierarchical graphs, 320-331 [Zbl 1502.68225] \textit{Baeza-Yates, Ricardo; Régnier, Mireille}, Fast algorithms for two dimensional and multiple pattern matching (preliminary version), 332-347 [Zbl 1502.68354] \textit{Tarhio, Jorma; Ukkonen, Esko}, Boyer-Moore approach to approximate string matching (extended abstract), 348-359 [Zbl 1502.68381] \textit{Grape, Per}, Complete problems with \(L\)-samplable distributions, 360-367 [Zbl 1502.68128] \textit{Hershberger, John}, Upper envelope onion peeling, 368-379 [Zbl 1504.68259] \textit{Hershberger, John; Suri, Subhash}, Applications of a semi-dynamic convex hull algorithm, 380-392 [Zbl 1502.68324] \textit{van Kreveld, Marc; Overmars, Mark; Agarwal, Pankaj K.}, Intersection queries in sets of disks, 393-403 [Zbl 1502.68349] \textit{Schipper, Haijo; Overmars, Mark H.}, Dynamic partition trees, 404-417 [Zbl 1502.68342]