Skip to main content
SpringerLink
Log in

Algorithms and Complexity

4th Italian Conference, CIAC 2000 Rome, Italy, March 1-3, 2000 Proceedings

  • Conference proceedings
  • © 2000

Overview

Editors:
  1. Giancarlo Bongiovanni

    1. Department of Computer Science, University of Rome “La Sapienza”, Rome, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. Rossella Petreschi

    1. Department of Computer Science, University of Rome “La Sapienza”, Rome, Italy

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. Giorgio Gambosi

    1. Department of Mathematics, University of Rome “Tor Vergata”, Rome, Italy

    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 1767)

Included in the following conference series:

Conference proceedings info: CIAC 2000.

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

Access this book

Log in via an institution
eBook USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
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 (25 papers)

  1. Front Matter

    Pages I-VIII
    Download chapter PDF

  2. Invited Presentations

    1. On Salesmen, Repairmen, Spiders, and Other Traveling Agents

      • Giorgio Ausiello, Stefano Leonardi, Alberto Marchetti-Spaccamela
      Pages 1-16

    2. Computing a Diameter-Constrained Minimum Spanning Tree in Parallel

      • Narsingh Deo, Ayman Abdalla
      Pages 17-31

    3. Algorithms for a Simple Point Placement Problem

      • Joshua Redstone, Walter L. Ruzzo
      Pages 32-43

    4. Duality in ATM Layout Problems

      • Shmuel Zaks
      Pages 44-58

  3. Regular Presentations

    1. The Independence Number of Random Interval Graphs

      • W. de la Vega Fernandez
      Pages 59-62

    2. Online Strategies for Backups

      • Peter Damaschke
      Pages 63-71

    3. Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem

      • Hans-Joachim Böckenhauer, Juraj Hromkovič, Ralf Klasing, Sebastian Seibert, Walter Unger
      Pages 72-86

    4. Semantical Counting Circuits

      • Fabrice Noilhan, Miklos Santha
      Pages 87-101

    5. The Hardness of Placing Street Names in a Manhattan Type Map

      • Sebastian Seibert, Walter Unger
      Pages 102-112

    6. Labeling Downtown

      • Gabriele Neyer, Frank Wagner
      Pages 113-124

    7. The Online Dial-a-Ride Problem under Reasonable Load

      • Dietrich Hauptmeier, Sven O. Krumke, Jörg Rambau
      Pages 125-136

    8. The Online-TSP against Fair Adversaries

      • Michiel Blom, Sven O. Krumke, Willem de Paepe, Leen Stougie
      Pages 137-149

    9. QuickHeapsort, an Efficient Mix of Classical Sorting Algorithms

      • Domenico Cantone, Gianluca Cincotti
      Pages 150-162

    10. Triangulations without Minimum-Weight Drawing

      • Cao An Wang, Francis Y. Chin, Boting Yang
      Pages 163-173

    11. Faster Exact Solutions for Max2Sat

      • Jens Gramm, Rolf Niedermeier
      Pages 174-186

    12. Dynamically Maintaining the Widest k-Dense Corridor

      • Subhas C. Nandy, Tomohiro Harayama, Tetsuo Asano
      Pages 187-198

    13. Reconstruction of Discrete Sets from Three or More X-Rays

      • Elena Barcucci, Sara Brunetti, Alberto Del Lungo, Maurice Nivat
      Pages 199-210

    14. Modified Binary Searching for Static Tables

      • Donatella Merlini, Renzo Sprugnoli, M. Cecilia Verri
      Pages 211-225

    15. An Efficient Algorithm for the Approximate Median Selection Problem

      • Sebastiano Battiato, Domenico Cantone, Dario Catalano, Gianluca Cincotti, Micha Hofri
      Pages 226-238
Back to top

Other volumes

  1. Algorithms and Complexity

Keywords

About this book

The papers in this volume were presented at the Fourth Italian Conference on Algorithms and Complexity (CIAC 2000). The conference took place on March 1-3, 2000, in Rome (Italy), at the conference center of the University of Rome \La Sapienza". This conference was born in 1990 as a national meeting to be held every three years for Italian researchers in algorithms, data structures, complexity, and parallel and distributed computing. Due to a signi cant participation of foreign reaserchers, starting from the second conference, CIAC evolved into an international conference. In response to the call for papers for CIAC 2000, there were 41 subm- sions, from which the program committee selected 21 papers for presentation at the conference. Each paper was evaluated by at least three program committee members. In addition to the selected papers, the organizing committee invited Giorgio Ausiello, Narsingh Deo, Walter Ruzzo, and Shmuel Zaks to give plenary lectures at the conference. We wish to express our appreciation to all the authors of the submitted papers, to the program committee members and the referees, to the organizing committee, and to the plenary lecturers who accepted our invitation.

Editors and Affiliations

  • Department of Computer Science, University of Rome “La Sapienza”, Rome, Italy

    Giancarlo Bongiovanni, Rossella Petreschi

  • Department of Mathematics, University of Rome “Tor Vergata”, Rome, Italy

    Giorgio Gambosi

Bibliographic Information

Publish with us

Policies and ethics

Back to top

Search

Navigation