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

Front Cover
Springer Science & Business Media, May 15, 2003 - Computers - 288 pages
The papers in this volume were presented at the 5th Italian Conference on AlgorithmsandComplexity(CIAC2003). Theconferencetookplaceduring May 28-30, 2003, in Rome, Italy, at the Conference Centre of the University of Rome "La Sapienza. " CIAC started in 1990 as a national meeting to be held every three years for Italian researchers in algorithms, data structures, complexity theory, and parallelanddistributedcomputing. Duetoasigni?cantparticipationofforeign researchers, starting from the second edition, CIAC evolved into an international conference. However, alltheeditionsofCIAChavebeenheldinRome. The proceedings of CIAC were published by World Scienti?c for the ?rst edition and by Springer-Verlag in the Lecture Notes in Computer Science series (volumes 778,1203and1767)forthesubsequenteditions. Aselectionofthepapersofthe fourth edition was published in a special issue of Theoretical Computer Science Vol. 285(1),2002. Thisyearweexpecttopublishanextendedversionofselected papers presented at the conference in a special issue of the journal Theory of Computing Systems. In response to the call for papers for CIAC 2003, 57 papers were subm- ted, from which the Program Committee selected 23 papers for presentation at theconferencefrom18countries. Eachpaperwasevaluatedbyatleastthree Program Committee members with the help of 63 external reviewers. In addition to the selected papers, the Organizing Committee invited CharlesE. Leiserson(Cambridge), DavidPeleg(Rehovot), MichaelO. Rabin (CambridgeandJerusalem), JohnE. Savage(Providence), andLucaTrevisan (Berkeley)togiveplenarylecturesattheconference. Moreover, threetutorials byDavidPeleg, JaymeL. Szwarc?ter(RiodeJaneiro)andLucaTrevisanwere o?ered in the days preceding the conference. We wish to express our appreciation to all the authors of the submitted - pers, to the Program Committee members and the referees, to the Organizing Committee, and to the plenary and tutorial lecturers who accepted our in- tation.
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Localized Network Representations
1
Optimal Binary Search Trees with Costs Depending on the Access Paths
2
On the Generation of Extensions of a Partially Ordered Set
3
ErrorCorrecting Codes in Complexity Theory
4
CacheOblivious Algorithms
5
Spanning Trees with Low MaximumAverage Stretch
6
Hyper Encryption and Everlasting Secrets
7
Computing with Electronic Nanotechnologies
11
Reconciling Gene Trees to a Species Tree
120
Generating All Forest Extensions of a Partially Ordered Set
132
Indexing Structures for Approximate String Matching
140
Approximation Hardness for Small Occurrence Instances of NPHard Problems
152
Fast Approximation of Minimum Multicast Congestion Implementation versus Theory
165
Approximation of a Retrieval Problem for Parallel Disks
178
On kEdgeConnectivity Problems with Sharpened Triangle Inequality
189
The Complexity of Detecting FixedDensity Clusters
201

Efficient Update Strategies for Geometric Computing with Uncertainty
12
Maximizing the Guarded Boundary of an Art Gallery Is APXComplete
24
An Improved Algorithm for Point Set Pattern Matching under Rigid Motion
36
Unlocking the Advantages of Dynamic Service Selection and Pricing
46
The Relative Worst Order Ratio for OnLine Algorithms
58
OnLine Stream Merging Max Span and Min Coverage
70
Randomised Algorithms for Finding Small WeaklyConnected Dominating Sets of Regular Graphs
83
Additive Spanners for kChordal Graphs
96
FixedParameter Algorithms for Clique Generation
108
Nearly Bounded Error Probabilistic Sets
213
Some Properties of MODm Circuits Computing Simple Functions
227
XORBased Schemes for Fast Parallel IP Lookups
238
The Impact of Network Structure on the Stability of Greedy Protocols
251
Improving Customer Proximity to Railway Stations
264
Differential Approximation for Some Routing Problems
277
Author Index
289
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information