Algorithms and complexity : 4th Italian conference, CIAC 2000, Rome, Italy, March 1 3, 2000 : proceedings | Italian Conference on Algorithms and Complexity (4th : 2000 : Rome, Italy), Bongiovanni, Giancarlo, Gambosi, G. (Giorgio), 1955-, Petreschi, Rossella, 1950-

Algorithms and Complexity: 4th Italian Conference, CIAC 2000 Rome, Italy, March 1–3, 2000 Proceedings
Author: Giancarlo Bongiovanni, Rossella Petreschi, Giorgio Gambosi
Published by Springer Berlin Heidelberg
ISBN: 978-3-540-67159-6
DOI: 10.1007/3-540-46521-9

Table of Contents:

• On Salesmen, Repairmen, Spiders, and Other Traveling Agents
• Computing a Diameter-Constrained Minimum Spanning Tree in Parallel
• Algorithms for a Simple Point Placement Problem
• Duality in ATM Layout Problems
• The Independence Number of Random Interval Graphs
• Online Strategies for Backups
• Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem
• Semantical Counting Circuits
• The Hardness of Placing Street Names in a Manhattan Type Map
• Labeling Downtown
• The Online Dial-a-Ride Problem under Reasonable Load
• The Online-TSP against Fair Adversaries
• QuickHeapsort, an Efficient Mix of Classical Sorting Algorithms
• Triangulations without Minimum-Weight Drawing
• Faster Exact Solutions for Max2Sat
• Dynamically Maintaining the Widest k-Dense Corridor
• Reconstruction of Discrete Sets from Three or More X-Rays
• Modified Binary Searching for Static Tables
• An Efficient Algorithm for the Approximate Median Selection Problem
• Extending the Implicit Computational Complexity Approach to the Sub-elementary Time-Space Classes

Includes bibliographical references and index