Algorithms and Complexity: 5th Italian Conference, CIAC 2003, Rome, Italy, May 28-30, 2003, ProceedingsThis 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. |
Contents
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 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 chordal graph CIAC circuit clique Cluster competitive ratio complexity Computer Science consider constant construct convex hull convex hull areas corresponding cost currentlevel cycle deleted denote differential approximation dominating set edges equations exists factor First-Fit function gene tree given graph G guard 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 Steiner tree stream subgraph subtree Theorem tree spanners triangle inequality update vertex vertices worst order ratio Worst-Fit