Algorithms and Complexity: 5th Italian Conference, CIAC 2003, Rome, Italy, May 28–30, 2003. Proceedings

David Peleg (auth.), Rossella Petreschi, Giuseppe Persiano, Riccardo Silvestri (eds.)3540401768, 9783540401766

This book constitutes the refereed proceedings of the 5th Italian Conference on Algorithms and Computation, CIAC 2003, held in Rome, Italy in May 2003.

The 23 revised full papers presented were carefully reviewed and selected from 57 submissions. Among the topics addressed are complexity, complexity theory, geometric computing, matching, online algorithms, combinatorial optimization, computational graph theory, approximation algorithms, network algorithms, routing, and scheduling.

---

Table of contents :
Localized Network Representations….Pages 1-1
Optimal Binary Search Trees with Costs Depending on the Access Paths….Pages 2-2
On the Generation of Extensions of a Partially Ordered Set….Pages 3-3
Error-Correcting Codes in Complexity Theory….Pages 4-4
Cache-Oblivious Algorithms….Pages 5-5
Spanning Trees with Low Maximum/Average Stretch….Pages 6-6
Hyper Encryption and Everlasting Secrets….Pages 7-10
Computing with Electronic Nanotechnologies….Pages 11-11
Efficient Update Strategies for Geometric Computing with Uncertainty….Pages 12-23
Maximizing the Guarded Boundary of an Art Gallery Is APX-Complete….Pages 24-35
An Improved Algorithm for Point Set Pattern Matching under Rigid Motion….Pages 36-45
Unlocking the Advantages of Dynamic Service Selection and Pricing….Pages 46-57
The Relative Worst Order Ratio for On-Line Algorithms….Pages 58-69
On-Line Stream Merging, Max Span, and Min Coverage….Pages 70-82
Randomised Algorithms for Finding Small Weakly-Connected Dominating Sets of Regular Graphs….Pages 83-95
Additive Spanners for k -Chordal Graphs….Pages 96-107
Graph-Modeled Data Clustering: Fixed-Parameter Algorithms for Clique Generation….Pages 108-119
Reconciling Gene Trees to a Species Tree….Pages 120-131
Generating All Forest Extensions of a Partially Ordered Set….Pages 132-139
Indexing Structures for Approximate String Matching….Pages 140-151
Approximation Hardness for Small Occurrence Instances of NP-Hard Problems….Pages 152-164
Fast Approximation of Minimum Multicast Congestion — Implementation versus Theory….Pages 165-177
Approximation of a Retrieval Problem for Parallel Disks….Pages 178-188
On k -Edge-Connectivity Problems with Sharpened Triangle Inequality….Pages 189-200
The Complexity of Detecting Fixed-Density Clusters….Pages 201-212
Nearly Bounded Error Probabilistic Sets….Pages 213-226
Some Properties of MOD m Circuits Computing Simple Functions….Pages 227-237
XOR-Based Schemes for Fast Parallel IP Lookups….Pages 238-250
The Impact of Network Structure on the Stability of Greedy Protocols….Pages 251-263
Improving Customer Proximity to Railway Stations….Pages 264-276
Differential Approximation for Some Routing Problems….Pages 277-288