Skip to main content
SpringerLink
Log in

Algorithm Theory - SWAT '92

Third Scandinavian Workshop on Algorithm Theory, Helsinki, Finland, July 8-10, 1992. Proceedings

  • Conference proceedings
  • © 1992

Overview

Editors:
  1. Otto Nurmi
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Esko Ukkonen
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Lecture Notes in Computer Science (LNCS, volume 621)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
Softcover Book USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (38 papers)

  1. Front Matter

    Download chapter PDF

  2. Direct bulk-synchronous parallel algorithms

    • Alexandras V. Gerbessiotis, Leslie G. Valiant
    Pages 1-18

  3. Memory limited inductive inference machines

    • Rūsinš Freivalds, Carl H. Smith
    Pages 19-29

  4. Retrieval of scattered information by EREW, CREW and CRCW PRAMs

    • Faith Fich, Miroslaw Kowaluk, Krzysztof Loryś, Miroslaw Kutylowski, Prabhakar Ragde
    Pages 30-41

  5. On small depth threshold circuits

    • Alexander A. Razborov
    Pages 42-52

  6. An elementary approach to some analytic asymptotics

    • Nicholas Pippenger
    Pages 53-61

  7. An optimal parallel algorithm for computing a near-optimal order of matrix multiplications

    • Artur Czumaj
    Pages 62-72

  8. Generating sparse 2—spanners

    • Guy Kortsarz, David Peleg
    Pages 73-82

  9. Low-diameter graph decomposition is in NC

    • Baruch Awerbuch, Bonnie Berger, Lenore Cowen, David Peleg
    Pages 83-93

  10. Parallel algorithm for cograph recognition with applications

    • Xin He
    Pages 94-105

  11. Parallel algorithms for all minimum link paths and link center problems

    • Subir Kumar Ghosh, Anil Maheshwari
    Pages 106-117

  12. Optimal multi-packet routing on the torus

    • Michael Kaufmann, Jop F. Sibeyn
    Pages 118-129

  13. Parallel algorithms for priority queue operations

    • Maria Cristina Pinotti, Geppino Pucci
    Pages 130-139

  14. Heap construction in the parallel comparison tree model

    • Paul F. Dietz
    Pages 140-150

  15. Efficient rebalancing of chromatic search trees

    • Joan Boyar, Kim S. Larsen
    Pages 151-164

  16. The complexity of scheduling problems with communication delays for trees

    • Andreas Jakoby, Rüdiger Reischuk
    Pages 165-177

  17. The list update problem and the retrieval of sets

    • Fabrizio d'Amore, Vincenzo Liberatore
    Pages 178-191

  18. Gkd-trees: Binary trees that combine multi-dimensional data handling, node size and fringe reorganization

    • Walter Cunto, Vicente Yriarte
    Pages 192-211

  19. Fractional cascading simplified

    • Sandeep Sen
    Pages 212-220

  20. Dynamic 2- and 3-connectivity on planar graphs

    • Dora Giammarresi, Giuseppe F. Italiano
    Pages 221-232
Back to top

Keywords

About this book

The papers in this volume were presented at SWAT 92, the Third Scandinavian Workshop on Algorithm Theory. The workshop, which continues the tradition ofSWAT 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 volume contains invited papers by L.G. Valiant (Direct bulk-synchronous parallel algorithms), A.A. Razborov (On small depth threshold circuits), G. Gonnet (Efficient two-dimensional searching), and E. Welzl (New results on linear programming and related problems), together with 34 selected contributed papers. Contributions cover algorithms and data structures in all areas, including combinatorics, computational geometry, data bases, parallel and distributed computing, and graphics.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation