Algorithms and Complexity

by Italian Conference on Algorithms and Complexity (4th : 2000 : Rome, Italy); Bongiovanni, Giancarlo; Gambosi, G.

• ISBN13: 9783540671596
• ISBN10: 3540671595
• eBook ISBN(s): 9783540465218
• Format: Paperback
• Copyright: 2000-03-01
• Publisher: Springer Verlag
• More Book Details
• Purchase Benefits

Summary

This book constitutes the refereed proceedings of the 4th Italian Conference on Algorithms and Complexity, CIAC 2000, held in Rome, Italy, in March 2000.The 21 revised full papers presented were carefully reviewed and selected from 41 submissions; also included are four invited survey papers. Among the topics addressed are combinatorial optimization, graph algorithms, graph computations, complexity theory, diagram design, approximation, scheduling, sorting, computational geometry, searching, and pattern matching.

Table of Contents

Invited Presentations
On Salesmen, Repairmen, Spiders, and Other Traveling Agents	p. 1
Computing a Diameter-Constrained Minimum Spanning Tree in Parallel	p. 17
Algorithms for a Simple Point Placement Problem	p. 32
Duality in ATM Layout Problems	p. 44
Regular Presentations
The Independence Number of Random Interval Graphs	p. 59
Online Strategies for Backups	p. 63
Towards the Notion of Stability of Approximation for Hard Optimization Tasks and the Traveling Salesman Problem	p. 72
Semantical Counting Circuits	p. 87
The Hardness of Placing Street Names in a Manhattan Type Map	p. 102
Labeling Downtown	p. 113
The Online Dial-a-Ride Problem under Reasonable Load	p. 125
The Online-TSP against Fair Adversaries	p. 137
QuickHeapsort, an Efficient Mix of Classical Sorting Algorithms	p. 150
Triangulations without Minimum-Weight Drawing	p. 163
Faster Exact Solutions for Max2Sat	p. 174
Dynamically Maintaining the Widest k-Dense Corridor	p. 187
Reconstruction of Discrete Sets from Three or More X-Rays	p. 199
Modified Binary Searching for Static Tables	p. 211
An Efficient Algorithm for the Approximate Median Selection Problem	p. 226
Extending the Implicit Computational Complexity Approach to the Sub-elementary Time-Space Classes	p. 239
Group Updates for Red-Black Trees	p. 253
Approximating SVP8 to within Almost-Polynomial Factors Is NP-Hard	p. 263
Convergence Analysis of Simulated Annealing-Based Algorithms Solving Flow Shop Scheduling Problems	p. 277
On the Lovász Number of Certain Circulant Graphs	p. 291
Speeding Up Pattern Matching by Text Compression	p. 306
Author Index	p. 317
Table of Contents provided by Publisher. All Rights Reserved.