Algorithms and Complexity: 4th Italian Conference, CIAC 2000 Rome, Italy, March 1–3, 2000 ProceedingsAuthor: Giancarlo Bongiovanni, Rossella Petreschi, Giorgio Gambosi Published by Springer Berlin Heidelberg ISBN: 978-3-540-67159-6 DOI: 10.1007/3-540-46521-9Table 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