## Algorithms and Complexity: 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, Proceedings, Volume 5The 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 |

289 | |

### Other editions - View all

Algorithms and Complexity Rosella Petreschi,Giuseppe Persiano,Riccardo Silvestri No preview available - 2014 |

### Common terms and phrases

adversary Any-Fit algorithm approximation algorithms Art Gallery problem bandwidth Berlin Heidelberg 2003 Bin Packing Problem chordal graph CIAC circuit clique competitive ratio complexity Computer Science consider constant construct contains convex hull convex hull areas corresponding cost currentlevel cycle deleted denote differential approximation edges equations exists factor First-Fit function gene tree given graph G input instance integer k-edge-connected kVRP label least Lemma length line segments LNCS lower bound machine matching Max Gain maximal maximum minimum MOD2 MODp Nearly-BPP node NP-complete NP-hard on-line online algorithm optimal solution packets Packing Problem parameter path Petreschi polygon polynomial polynomial-time Proc Proof queues random reconciled tree relative worst order routing table sequence service providers sharpened triangle inequality spanners species tree stations Steiner tree stream subgraph subtree Theorem tree spanners triangle inequality update vertices worst order ratio Worst-Fit