Skip to main content
SpringerLink
Log in

Algorithms and Complexity

Second Italian Conference, CIAC '94, Rome, Italy, February 23 - 25, 1994. Proceedings

  • Conference proceedings
  • © 1994

Overview

Editors:
  1. M. Bonuccelli
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. P. Crescenzi
    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. R. Petreschi
    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 778)

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 (18 papers)

  1. Front Matter

    Download chapter PDF

  2. On the intellectual terrain around NP

    • Juris Hartmanis, Suresh Chari
    Pages 1-11

  3. Advances in graph drawing

    • Ashim Garg, Roberto Tamassia
    Pages 12-21

  4. On a parallel-algorithms method for string matching problems (overview)

    • Suleyman Cenk Sahinalp, Uzi Vishkin
    Pages 22-32

  5. Some open problems in approximation

    • Mihalis Yannakakis
    Pages 33-39

  6. New local search approximation techniques for maximum generalized satisfiability problems

    • Paola Alimonti
    Pages 40-53

  7. Learning behaviors of automata from multiplicity and equivalence queries

    • F. Bergadano, S. Varricchio
    Pages 54-62

  8. Measures of Boolean function complexity based on Harmonic Analysis

    • A. Bernasconi, B. Codenotti
    Pages 63-72

  9. Graph theory and interactive protocols for Reachability Problems on finite Cellular automata

    • A. Clementi, R. Impagliazzo
    Pages 73-90

  10. Parallel pruning decomposition (PDS) and biconnected components of graphs

    • Eliezer Dekel, Jie Hu
    Pages 91-108

  11. A non-interactive electronic cash system

    • Giovanni Di Crescenzo
    Pages 109-124

  12. A unified scheme for routing in expander based networks

    • Shimon Even, Ami Litman
    Pages 125-135

  13. Dynamization of backtrack-free search for the constraint satisfaction problem

    • Daniele Frigioni, Alberto Marchetti-Spaccamela, Umberto Nanni
    Pages 136-151

  14. Efficient reorganization of binary search trees

    • Micha Hofri, Hadas Shachnai
    Pages 152-166

  15. Time-message trade-offs for the weak unison problem

    • Amos Israeli, Evangelos Kranakis, Danny Krizanc, Nicola Santoro
    Pages 167-178

  16. On set equality-testing

    • Tak Wah Lam, Ka Hing Lee
    Pages 179-191

  17. On the complexity of some reachability problems

    • Angelo Monti, Alessandro Roncato
    Pages 192-202

  18. On self-reducible sets of low information content

    • Martin Mundhenk
    Pages 203-212

  19. Lower bounds for merging on the hypercube

    • Christine Rüb
    Pages 213-222

  20. Back Matter

    Download chapter PDF
Back to top

Keywords

About this book

The papers in this volume were presented at the Second Italian Conference onAlgorithms and Complexity, held in February 1994 in Rome. This biannual conference series is intended to present research contributions in theory and applications of sequential, parallel, and distributed algorithms, data structures, and computational complexity. The volume contains four invited presentations and 14 regular presentations selected from 32 submissions, each of which was evaluated by at least four program committee members. The invited presentations are by J. Hartmanis and S. Chari, A. Garg and R. Tamassia, S.C. Sahinalp and U. Vishkin, and M. Yannakakis.

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation