3. CIAC 1997: Rome, Italy

Invited Presentations

• Gianfranco Bilardi:
  Algorithms and Data Structures for Control Dependence and Related Compiler Problems. 1-2
  
• Guy Even, Shimon Even:
  Embedding Interconnection Networks in Grids via the Layered Cross Product. 3-12
  

Regular Presentations

• Yefim Dinitz, Zeev Nutov:
  Finding Optimum k-vertex Connected Spanning Subgraphs: Improved Approximation Algorithms for k=3, 4, 5. 13-24
  
• Klaus Jansen:
  The Optimum Cost Chromatic Partition Problem. 25-36
  
• Samir Khuller, Robert Pless, Yoram J. Sussmann:
  Fault Tolerant K-Center Problems. 37-48
  
• Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel:
  R^SN_1-tt(NP) Distinguishes Robust Many-One and Turing Completeness. 49-60
  
• Salvatore Caporaso, Michele Zito, Nicola Galesi, Emanuele Covino:
  Syntactic Characterization in LISP of the Polynominal Complexity Classes and Hierarchy. 61-73
  
• Uriel Feige, Giora Rayzman:
  On the Drift of Short Schedules. 74-85
  
• Francisco Gómez, Suneeta Ramaswami, Godfried T. Toussaint:
  On Removing Non-degeneracy Assumptions in Computational Geometry. 86-99
  
• Fabrizio d'Amore, Paolo Giulio Franciosa, Roberto Giaccio, Maurizio Talamo:
  Maintaining Maxima under Boundary Updates. 100-109
  
• Amitava Datta, Kamala Krithivasan, Thomas Ottmann:
  An Optimal Algorithm for One-Separation of a Set of Isothetic Polygons. 110-121
  
• Ulrich Fößmeier, Michael Kaufmann:
  Nice Drawings for Planar Bipartite Graphs. 122-134
  
• Giuseppe Liotta, Roberto Tamassia, Ioannis G. Tollis, Paola Vocca:
  Area Requirement of Gabriel Drawings. 135-146
  
• Fabrizio Luccio, Alberto Pedrotti:
  Design of Reliable Combinatorial Algorithms Using Certificates. 147-158
  
• Amihood Amir, Emanuel Dar:
  An Improved Deterministic Algorithms for Generalized Random Sampling. 159-170
  
• Carlos Domingo:
  Polynominal Time Algorithms for Some Self-Duality Problems. 171-180
  
• Paolo Ferragina, Roberto Grossi, Manuela Montangero:
  A Note on Updating Suffix Tree Labels. 181-192
  
• Sabine Hanke, Thomas Ottmann, Eljas Soisalon-Soininen:
  Relaxed Balanced Red-Black Trees. 193-204
  
• Peter Damaschke:
  The Algorithmic Complexity of Chemical Threshold Testing. 205-216
  
• Jyrki Katajainen, Jesper Larsson Träff:
  A Meticulous Analysis of Mergesort Programs. 217-228
  
• Jop F. Sibeyn, Michael Kaufmann:
  BSP-Like External-Memory Computation. 229-240
  
• Gianpiero Cattaneo, Michele Finelli, Luciano Margara:
  Topological Chaos for Elementary Cellular Automata. 241-252
  
• Anna Bernasconi:
  On the Complexity of Balanced Boolean Functions. 253-263
  
• Lane A. Hemaspaandra, Jörg Rothe, Gerd Wechsung:
  On Sets with Easy Certificates and the Existence of One-Way Permutations. 264-275
  
• Koichi Yamazaki, Hans L. Bodlaender, Babette de Fluiter, Dimitrios M. Thilikos:
  Isomorphism for Graphs of Bounded Distance Width. 276-287
  
• Paola Alimonti, Viggo Kann:
  Hardness of Approximating Problems on Cubic Graphs. 288-298
  
• Ming-Yang Kao:
  Tree Contractions and Evolutionary Trees. 299-310