4. LATIN 2000: Punta del Este, Uruguay

@proceedings{DBLP:conf/latin/2000,
  editor    = {Gaston H. Gonnet and
               Daniel Panario and
               Alfredo Viola},
  title     = {LATIN 2000: Theoretical Informatics, 4th Latin American Symposium,
               Punta del Este, Uruguay, April 10-14, 2000, Proceedings},
  booktitle = {LATIN},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {1776},
  year      = {2000},
  isbn      = {3-540-67306-7},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Random Structures and Algorithms

• Yoshiharu Kohayakawa, Vojtech Rödl: Algorithmic Aspects of Regularity. 1-17
• Michele Zito: Small Maximal Matchings in Random Graphs. 18-27
• Vlady Ravelomanana, Loÿs Thimonier: Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs. 28-37
• Andreas Goerdt, Michael Molloy: Analysis of Edge Deletion Processes on Faulty Random Regular Graphs. 38-47
• Yoshiharu Kohayakawa, Vojtech Rödl, Jozef Skokan: Equivalent Conditions for Regularity (Extended Abstract). 48-57

Algorithms I

• Flávio Keidi Miyazawa, Yoshiko Wakabayashi: Cube Packing. 58-67
• Klaus Jansen, Monaldo Mastrolilli, Roberto Solis-Oba: Approximation Algorithms for Flexible Job Shop Problems. 68-77
• Stephen Taylor: Emerging Behavior as Binary Search Trees Are Symmetrically Updated. 78-87
• Michael A. Bender, Martin Farach-Colton: The LCA Problem Revisited. 88-94

Combinatorial Designs

• Myra B. Cohen, Charles J. Colbourn: Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays. 95-104
• Lucia Moura: Rank Inequalities for Packing Designs and Sparse Triple Systems. 105-114
• Brett Stevens: The Anti-Oberwolfach Solution: Pancyclic 2- Factorizations of Complete Graphs. 115-122

Web Graph, Graph Theory I

• Prabhakar Raghavan: Graph Structure of the Web: A Survey. 123-125
• Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce A. Reed, Udi Rotics: Polynomial Time Recognition of Clique-Width \le \leq 3 Graphs (Extended Abstract). 126-134
• Cláudia Linhares Sales, Frédéric Maffray: On Dart-Free Perfectly Contractile Graphs. Extended Abstract. 135-144

Graph Theory II

• Celina M. Herrera de Figueiredo, Célia Picinin de Mello, Carmen Ortiz: Edge Colouring Reduced Indifference Graphs. 145-153
• David Avis, Caterina De Simone, Paolo Nobili: Two Conjectures on the Chromatic Polynomial. 154-162
• Celina M. Herrera de Figueiredo, Sulamita Klein, Yoshiharu Kohayakawa, Bruce A. Reed: Finding Skew Partitions Efficiently. 163-172

Competitive Analysis, Complexity

• Allan Borodin, Ran El-Yaniv, Vincent Gogan: On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract). 173-196
• Valentine Kabanets: Almost k-Wise Independence and Hard Boolean Functions. 197-206
• Andris Ambainis, Satyanarayana V. Lokam: Imroved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function. 207-216

Algorithms II

• David Fernández-Baca: Multi-parameter Minimum Spanning Trees. 217-226
• Ruy Luiz Milidiú, Eduardo Sany Laber: Linear Time Recognition of Optimal L-Restricted Prefix Codes (Extended Abstract). 227-236
• Jaroslav Opatrny: Uniform Multi-hop All-to-All Optical Routings in Rings. 237-246
• Serafino Cicerone, Gabriele Di Stefano, Daniele Frigioni, Umberto Nanni: A Fully Dynamic Algorithm for Distributed Shortest Paths. 247-257

Computational Number Theory, Cryptography

• Andrew M. Odlyzko: Integer Factorization and Discrete Logarithms (Abstract). 258
• Igor Shparlinski: Communication Complexity and Fourier Coefficients of the Diffie-Hellman Key. 259-268
• Pedro Berrizbeitia, Mauricio Odremán Vera, Juan Tena Ayuso: Quintic Reciprocity and Primality Test for Numbers of the Form M = A5ⁿ±omega_n. 269-279
• Matthias Krause, Hans-Ulrich Simon: Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography. 280-291

Analysis of Algorithms I

• Edward G. Coffman Jr., George S. Lueker, Joel Spencer, Peter M. Winkler: Average-Case Analysis of Retangle Packings. 292-297
• Charles Knessl, Wojciech Szpankowski: Heights in Generalized Tries and PATRICIA Tries. 298-307
• Dominique Barth, Sylvie Corteel, Alain Denise, Danièle Gardy, Mario Valencia-Pabon: On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths. Extended Abstract. 308-317

Algebraic Algorithms

• Joachim von zur Gathen, Thomas Lücking: Subresultants Revisited. 318-342
• Brigitte Vallée: A Unifying Framework for the Analysis of a Class of Euclidean Algorithms. 343-354
• Ali Akhavi: Worst-Case Complexity of the Optimal LLL Algorithm. 355-366

Computability

• Stephen L. Bloom, Zoltán Ésik: Iteration Algebras Are Not Finitely Axiomatizable. Extended Abstract. 367-376
• Richard Mayr: Undecidable Problems in Unreliable Computations. 377-386

Automata, Formal Languages

• Claudio Gutiérrez: Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups. 387-396
• Marie-Pierre Béal, Olivier Carton, Christophe Prieur, Jacques Sakarovitch: Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers. 397-406
• Olivier Carton, Max Michel: Unambiguous Büchi Automata. 407-416
• Thomas Worsch: Linear Time Language Recognition on Cellular Automata with Restricted Communication. 417-426

Logic Programming Theory

• Luis R. Sierra Abbate, Pedro R. D'Argenio, Juan V. Echagüe: From Semantics to Spatial Distribution. 427-436
• François Laroussinie, Ph. Schnoebelen, Mathieu Turuani: On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics. 437-446
• Maribel Fernández, Ian Mackie: A Theory of Operational Equivalence for Interaction Nets. 447-456

Analysis of Algorithms II

• Peter J. Grabner, Arnold Knopfmacher, Helmut Prodinger: Run Statistics for Geometrically Distributed Random Variables (Extended Abstract). 457-462
• Guy Louchard: Generalized Covariances of Multi-dimensional Brownian Excursion Local Times. 463-472
• Helmut Prodinger: Combinatorics of Geometrically Distributed Random Variables: Lenght of Ascending Runs. 473-482