Lecture Notes in Computer Science 621 Edited by G. Goos and J. Hartmanis Advisory Board: W. Brauer D. Gries J. Stoer .O Nurmi E. Ukkonen (Eds.) mhtiroglA yroehT TAWS 29' Third Scandinavian Workshop on Algorithm Theory Helsinki, Finland, July 8-10, 2991 Proceedings galreV-regnirpS Berlin Heidelberg NewYork London Paris Tokyo Hong Kong Barcelona Budapest Series Editors Gerhard Goos Juris Hartmanis Universit~it Karlsruhe Department of Computer Science Postfach 69 80 Cornell University Vincenz-Priessnitz-Strage 1 5149 Upson Hall W-7500 Karlsruhe, FRG Ithaca, NY 14853, USA Volume Editors Otto Nurmi Esko Ukkonen Department of Computer Scence, University of Helsinki Teollisuuskatu 23, SF-00510 Hetsinki, Finland CR Subject Classification (1991): E1-2, E.1-2, G.2-3 ISBN 3-540-55706-7 Springer-Verlag Berlin Heidelberg New York ISBN 0-387-55706-7 Springer-Verlag New York Berlin Heidelberg This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting, reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Veflag. Violations are liable for prosecution under the German Copyright Law. (cid:14)9 Springer-Verlag Berlin Heidelberg 1992 Printed in Germany Typesetting: Camera ready by author/editor Printing and binding: Druckhaus Beltz, Hemsbach/Bergstr. 45/3140-543210 - Printed on acid-free paper Preface The papers in this volume were presented at SWAT '92, the Third Scandina- vian Workshop on Algorithm Theory. The workshop, which continues the tradition of SWAT '88, SWAT '90, and the Workshop on Algorithms and Data Structures (WADS '89, WADS '91), is intended as an international forum for researchers in the area of design and analysis of algorithms. The call for papers sought contributions in algorithms and data structures, in all areas, including combinatorics, compu- tational geometry, data bases, parallel and distributed computing, and graphics. There were 021 papers submitted, of which the program committee selected 43 for presentation. In addition, invited lectures were presented by Leslie .G Valiant (Di- rect bulk-synchronous parallel algorithms), Alexander A. Razborov (On small depth threshold circuits), Gaston Gonnet (Efficient two-dimensional searching), and Emo Welzl (New results on linear programming and related problems). SWAT 29' was held in ttelsinki, July 8-10, 1992, and saw organized in -oc operation with the Department of Computer Science of the University of ttelsinki. The organizing committee consisted of B. Aspvall (University of Bergen), .H Haf- steinsson (University of Iceland), .R Karlsson (Lund University), E. .M Schmidt (Aarhus University), O. Nurmi, J. Tarhio, and E. Ukkonen (University of Helsinki). The program committee wishes to thank all referees who aided in evaluating the papers. The organizers would like to thank J. Kivinen, .S Palander, and J. Vilo for excellent service in all organizational matters related to the conference. Finally, we are very grateful to Nordiska Forskarutbildningsakademin, Ministry of Education (Finland), the Academy of Finland, University of Helsinki, EATCS, the Finnish -oS ciety for Computer Science, NUS Microsystems ,yO and ICL Data Oy for sponsoring the workshop. Helsinki, May 2991 Otto Nurmi Esko Ukkonen Program Committee .S Arnborg (Royal Institute of Technology) .B Aspvall (University of Bergen) J. Gilbert (Xerox PARC and University of Bergen) T. Hagerup (Max-Planck-Institut) T. Leighton (MIT) .C Levcopoulos (Lund University) A. Lingas (Lund University) Th. Ottmann (University of Freiburg) .M Overmars (University of Utrecht) .M Penttonen (University of Joensuu) W. Rytter (University of Warsaw) .N Santoro (Carleton University) .S Skyum (Aarhus University) E. Ukkonen (chairman, University of Helsinki) List of Referees for SWAT '92 Alt, .H Kari, J. Munthe-Kaas, E. Anderson, .R Kari, .L Nevalainen, O. Bang-Jensen, J. Karlsson, R. Newman, I. Bodlaender, .H .L Karpinski, .M Nielsen, .M Boyar, J. Katajainen, J. Nilsson, .B Briiggemann-Klein, A. Kaufmann, .M Nurmi, O. Carlsson, .S Kivinen, J. Orponen, .P Casas, R. Klasing, R. Pennings, .M Chen, J. Klein, .R Raita, T. Chlebus, B. .S Kloks, T. Raman, R. Cole, R. Klr T. Reich, G. Cowen, .L J. Klugerman, .M Rossmanith, P. de Berg, .M Knuutila, T. Schirra, .S Dietzfelbinger, .M Kowaluk, .M Schmidt, E. Diks, .K Kozen, .D C. Schuierer, .S Eckerle, J. Kravets, .D Schwartzbach, .M Fleischer, .R Krogdahl, .S Schwarzkopf, O. Flor~en, P. Kunde, .M Singh, .M Forsell, .M Kutytowski, .M Smid, .M Frandsen, G. .S Lagergren, .S Syslo, .M Garrido, O. Langemyr, .L Szymacha, T. G~sieniec, .L Langholm, T. Tarhio, J. Goldmann, .M Laver, T. Teia, B. Golin, .M J. Lenhof, H.-P. Teuhola, J. Hs J. Lisper, B. Uhrig, .C Heinz, .A Luccio, F. van Kreveld, .M Huber-W~chle, F. Mannila, .H Veldhorst, .M Ihler, E. Mattsson, .C Vilo, J. Jennings, E. Mehlhorn, K. Voutilainen, .P Jonssons, .H Meiser, .S Wanka, R. Kahan, .S .H Miltersen, .P B. Welzl, E. Kant, G. Monien, .B Williamson, D. .P Karabeg, .D Mfiller, .N Winter, P. Table of Contents Direct Bulk-Synchronous Parallel Algorithms (Invited) A. V. Gerbessiotis and .51 G. Valiant .................................. 1 Memory Limited Inductive Inference Machines R. Freivalds and C. H. Smith ........................................ 91 Retrieval of Scattered Information by EREW, CREW and CRCW PRAMs F. Fich, M. Kowalnk, K. Lory~, M. Kntytowski, and P. Ragde ............ 03 On Small Depth Threshold Circuits (Invited) A. A. I~azborov .................................................... 24 An Elementary Approach to Some Analytic Asymptotics .Vi Pippenger ...................................................... 35 An Optimal Parallel Algorithm for Computing a Near-Optimal Order of Matrix Multiplications A. Cznmaj ........................................................ 26 Generating Sparse 2-Spanners G. Kortsarz and D. Peleg ........................................... 73 Low-Diameter Graph Decomposition si in NC B. Awerbuch, B. Berger, .51 Cowen, and D. Peleg ....................... 38 Parallel Algorithm for Cograph Recognition with Applications X. He ............................................................ 49 Parallel Algorithms for All Minimum Link Paths and Link Center Problems S. K. Ghosh and A. Maheshwari .................................... 601 Optimal Multi-Packet Routing on the Torus M. Kaufmann and J. F. Sibeyn ..................................... 811 Parallel Algorithms for Priority Queue Operations M. C. Pinotti and G. Pucci ........................................ 031 Heap Construction in the Parallel Comparison Tree Model P. F. Dietz ...................................................... 041 Efficient Rebalancing of Chromatic Search Trees J. Boyar and K. S. 15arsen ....... .................................. 151 The Complexity of Scheduling Problems with Communication Delays for Trees A. Jakoby and R. Reischnk ......................................... 561 The List Update Problem and" the Retrieval of Sets F. d'Amore and V. 15iberatore ...................................... 871 GKD-Trees: Binary Trees that Combine Multi-Dimensional Data Handling, Node Size, and Fringe Reorganization W. Cunlo and V. Yriarte .......................................... 291 Fractional Cascading Simplified S. Sen .......................................................... 212 Dynamic -2 and 3-Connectivity on Planar Graphs D. Giammarresi and G. F. Italiano .................................. 122 IIIV Fully Dynamic 2-Connectivity in Planar Graphs J. gershberger, M. Ranch, and S. Suri ............................... 233 Non-Interfering Network Flows C. McDiarmid, B. Reed, A. Schrijver, and B. Shepherd ................. 245 Triangulating Planar Graphs While Minimizing the Maximum Degree G. Kant and H. L. Bodlaender .................. .................... 258 How to Draw a Series-Parallel Digraph P. Bertolazzi, R. F. Cohen, G. Di Bat~ista, R. Tamassia, and L G. Tollis. 272 Coloring Random Graphs M. Filter and C. R. Subramanian .................................... 284 Testing Superperfection of k-Trees T. Kloks and H. Bodlaender ........................................ 292 Parametric Problems on Graphs of Bounded Tree-Width D. Ferndndez-Baca and G. Slutzki ................................... 304 Efficient Two-Dimensional Searching (Invited) G. Gonnet ....................................................... 317 Improvements on Geometric Pattern Matching Problems L. P. Chew and K. Kedem ......................................... 318 Determining DNA Sequence Similarity Using Maximum Independent Set Algorithms for Interval Graphs D. Joseph, J. Meidanis, and P. Tiwari ............................... 326 New Results on Linear Programming and Related Problems (Invited) E. Weld ......................................................... 338 Dynamic Closest Pairs -- A Probabilistic Approach M. J. Golin ...................................................... 340 Two- and Three-Dimensional Point Location in Rectangular Subdivisions M. de Berg, M. van Kreveld, and J. Snoeyink ......................... 352 Decomposing the Boundary of a Nonconvex Polyhedron B. Chazelle and L. Palios .......................................... 364 Convex Polygons Made from Few Lines and Convex Decompositions of Polyhedra J. Hershberger and J. Snoeyink ..................................... 376 Maintaining the Visibility Map of Spheres While Moving the Viewpoint on a Circle at Infinity H.-P. Lenhof and M. Staid ......................................... 388 Voronoi Diagrams of Moving Points in Higher Dimensional Spaces G. Albers and T. Roos ............................................. 399 Sorting Multisets Stably in Minimum Space J. Katajainen and T. Pasanen ...................................... 410 A Framework for Adaptive Sorting O. Petersson and A. Moffat ............................... ......... 422 Author Index ....................................................... 434 Direct Bulk-Synchronous Parallel Algorithms * Alexandros V. Gerbessiotis and Leslie .G Valiant Aiken Computation Laboratory Harvard University Cambridge, MA 02138, USA Abstract We describe a methodology for constructing parallel algorithms that are transportable among parallel computers having different numbers of processors, different bandwidths of interprocessor communication and different periodicity of global synchronisation. We do this for the bulk-synchronous parallel (BSP) model, which abstracts the characteristics of a parallel machine into three nu- merical parameters p, g, and L, corresponding to processors, bandwidth, and periodicity respectively. The model differentiates memory that is local to a processor from that which is not, but, for the sake of universality, does not dif- ferentiate network proximity. The advantages of this model in supporting shared memory or PRAM style programming have been treated elsewhere. Here we em- phasise the viability of an alternative direct style of programming where, for the sake of efficiency the programmer retains control of memory allocation. We show that optimality to within a multiplicative factor close to one can be achieved for the problems of Gauss-Jordan elimination and sorting, by transportable algo- rithms that can be applied for a wide range of values of the parameters p, g, and L. We also give some simulation results for PRAMs on the BSP to identify the level of slack at which corresponding efficiencies can be approached by shared memory simulations, provided the bandwidth parameter g is good enough. 1 The Model The bulk-synchronous parallel or BSP model as described in [17] consists of three parts: (i) a number of processor/memory components. Here we will assume that each con- sists of a sequential processor with a block of local memory. (ii) a router that can deliver messages (typically to implement read and write opera- tions) point to point among the components, and (iii) facilities for globally synchronizing, in barrier style, all or a subset of the compo- nents. The parameters of such a machine are p, the number of processor/memory com- ponents, L, the minimal time (measured in terms of basic local computation steps) *This research was supported in part by the National Science Foundation under grant CCR-89- 02500 and by the Of[ice of Naval Research under grant .5440-K-58-41000N between successive synchronization operations, and g the ratio of the total throughput of the whole system in terms of basic computational operations, to the throughput of the router in terms of words of information delivered. Computation on this model proceeds in a succession of supersteps. In each super- step each processor is given a task that can be executed using data already available there locally before the start of the superstep. The task may include local computa- tion steps, message transmissions and message receipts. To simplify the description of the performance of our algorithms, in this paper we shall assume that each superstep is either purely computation or purely communication (and not a mixture of both). In this way the two kinds of costs are easily separated. The model has two variants, depending on how synchronization is treated, that affect performance to multiplicative constant factors. In one the synchronizer checks at every L time units whether the tasks that are synchronized in the current superstep have all finished, and only when it discerns that they have does the machine proceed to the next superstep. In this paper, again for simplifying the analysis, we will use the alternative model where a superstep can complete any time after the first L units. More specifically, each superstep is charged max{L, z + hg) basic time units, where x is the maximum number of local computational steps executed by any processor, and h is the maximum number of packets that any processor sends or receives in that superstep. N.B. If hi is the maximum number sent and 2h the maximum number received we are taking h = max{hi, h2) here, although h = hi + h2 is possible too 16. Also how the expression for charging combines the z with the h is not crucial if, as we do here, we insist that each superstep is pure computation or pure communica- tion. We note that any particular machine may impose a lower bound on L for two reasons: There will be a minimum time requirement for doing synchronizations. Also the communication throughput specified by the chosen g may be realisable only for large enough L because of startup or latency considerations in routing. We note that although the model emphasizes global barrier style synchronization, pairs of proces- sors are always free to synchronize pairwise by, for example, sending messages to and from an agreed memory location. These message transmissions, however, would have to respect the superstep rules. 2 Background The BSP model was originally suggested as a possible "bridging" model to serve as a standard interface between the language and architecture levels in parallel com- putation. Two modes of programming were envisaged 17: automatic mode where programs are written in a high level language that hides memory distribution from the user (e.g. PRAM style), and direct mode where the programmer retains control of memory allocation. This paper is concerned with the direct mode. Since it is known that, under ap- propriate conditions, automatic mode achieves optimality to within constant factors, the primary question to ask is whether there are any circumstances at all in which the effort of programming in direct mode is warranted. We can identify four such circumstances: (a) where small multiplicative constant factors in runtime are important, (b) where smaller problem instances can be run efficiently in direct mode (i.e. less "slack" is sufficient) than in automatic mode, (c) where the available machine has a high g factor (since automatic mode generally requires g to be close to unity), and (d) where the available machine has an L that is sufficiently high for direct, but not for automatic mode, for the problem instance in hand. In light of the first of these conditions we emphasize multiplicative constant factors and in this paper ew restrict ourselves to one.optimal algorithms. Although it is generally problematic to measure complexity to this accuracy, since the operations that are counted have to be carefully defined, it can be made meaningful, if, as we do here, we measure ratios between runtimes on pairs of models that have the same set of local instructions. Thus we shall say that a BSP algorithm is one-optimal ni noitatupmoc if it performs the same number of operations, to a multiplicative factor of 1 + o(1) as n *-- c~, as a specified corresponding sequential or PRAM algorithm. Insistence on one-optimality leads to algorithms that only work in restricted ranges of n and L in terms of p. These ranges can. be extended in most cases, however, if the requirements are relaxed to, say, "two-optimality". We note that the role of a standard bridging model is as important in the direct programming context as in the automatic one. It will soon be inexpensive to augment workstations and personal computers with several processors. As long as efficient transportable software packages can be written for them, substantial reductions in runtime can be gained. We hypothesise that the BSP model, parametrised by p, L, and g and with direct control of memory distribution among the processors, is a simple enough model to serve this bridging role. One can foresee software packages to be written that can be run efficiently on a variety of machines for a wide range of values of these parameters. In these packages the algorithms would be parametrised by p, L, g, and the problem size n, in the same manner as we do in this paper. An efficient instance of the algorithm can be selected by a combination of compile-time and run-time decisions based on these parameters. The development and analysis of direct BSP algorithms has a secondary motiva- tion, one relating to computer architecture. A currently unresolved question is that of determining whether, if BSP computers are constructed in currently foreseeable technologies, it is efficacious to augment the global operations supported in hardware beyond the router, to, for example, broadcasting or the parallel prefix. To resolve this the complexities of some of the most frequently computed problems with respect to these various options need to be understood. 3 Communication Optimal Simulations In order to evaluate the usefulness of direct BSP algorithms we have to consider the best PRAM simulations with which they might compete. This competition is fairly stiff since, given sufficient slack, ew can find simulations that are one-optimal in communication operations and optimal to within small multiplicative constant factors in computational operations. By a PRAM simulation being one-optimal ni noitacinummoc we mean in particular that T(n) read/write operations of a PRAM