LATIN 2000: Theoretical Informatics: 4th Latin American Symposium, Punta del Este, Uruguay, April 10-14, 2000 Proceedings (Lecture Notes in Computer Science, 1776)

✍ Scribed by Gaston H. Gonnet (editor), Daniel Panario (editor), Alfredo Viola (editor)

• Publisher: Springer
• Year: 2000
• Tongue: English
• Leaves: 497
• Category: Library

✦ Synopsis

This volume contains the proceedings of the LATIN 2000 International Conference (LatinAmerican Theoretical INformatics), to be held in Punta del Este, Uruguay, April 10-14, 2000. This is the fourth event in the series following Sao ~ Paulo, Brazil (1992), Valparaíso, Chile (1995), and Campinas, Brazil (1998). LATIN has established itself as a fully refereed conference for theoretical computer science research in Latin America. It has also strengthened the ties between local and international scientific communities. We believe that this volume reflects the breadth and depth of this interaction. We received 87 submissions, from 178 different authors in 26 different countries. Eachpaperwasassignedtothreeprogramcommitteemembers.TheProgramCommittee selected 42 papers based on approximately 260 referee reports. In addition to these contributed presentations, the conference included six invited talks. The assistance of many organizations and individuals was essential for the success ofthismeeting.Wewouldliketothankallofoursponsorsandsupportingorganizations. Ricardo Baeza-Yates, Claudio Lucchesi, Arnaldo Moura, and Imre Simon provided - sightful advice and shared with us their experiences as organizers of previous LATIN meetings. Joaquín Goyoaga and Patricia Corbo helped in the earliest stages of the - ganization in various ways, including finding Uruguayan sources of financial support. SeCIU(ServicioCentraldeInformatica ´ Universitario, UniversidaddelaRepublica) ´ p- vided us with the necessary communication infrastructure. The meeting of the program committee was hosted by the Instituto de Matematica ´ e Estat stica, í Universidade de Sao ~ Paulo, which also provided us with the Intranet site for discussions among PC members.

✦ Table of Contents

Frontmatter
Random Structures and Algorithms
Algorithmic Aspects of Regularity
Small Maximal Matchings in Random Graphs
Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs
Analysis of Edge Deletion Processes on Faulty Random Regular Graphs
Equivalent Conditions for Regularity ~(Extended Abstract)
Algorithms I
Cube Packing
Approximation Algorithms for Flexible Job Shop Problems
Emerging Behavior as Binary Search Trees Are Symmetrically Updated
The LCA Problem Revisited
Combinatorial Designs
Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays
Rank Inequalities for Packing Designs and Sparse Triple Systems
The Anti-Oberwolfach Solution: Pancyclic 2-Factorizations of Complete Graphs
Web Graph, Graph Theory I
Graph Structure of the Web: A Survey
Polynomial Time Recognition of Clique-Width $\leq$~ 3 Graphs
On Dart-Free Perfectly Contractile Graphs Extended Abstract
Graph Theory II
Edge Colouring Reduced Indifference Graphs
Two Conjectures on the Chromatic Polynomial
Finding Skew Partitions Efficiently
Competitive Analysis, Complexity
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract)
Almost {\itshape k}-Wise Independence and Hard Boolean Functions
Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function
Algorithms II
Multi-parameter Minimum Spanning Trees
Linear Time Recognition of Optimal L-Restricted Prefix Codes
Uniform Multi-hop All-to-All Optical Routings in Rings
A Fully Dynamic Algorithm for Distributed Shortest Paths
Computational Number Theory, Cryptography
Integer Factorization and Discrete Logarithms
Communication Complexity and Fourier Coefficients of the Diffie--Hellman Key
Quintic Reciprocity and Primality Test for Numbers of the Form $M~=~A5^{n} \pm ~\omega_{n}$
Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography
Analysis of Algorithms I
Average-Case Analysis of Rectangle Packings
Heights in Generalized Tries and PATRICIA Tries
On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths Extended Abstract
Algebraic Algorithms
Subresultants Revisited
A Unifying Framework for the Analysis of a Class of Euclidean Algorithms
Worst-Case Complexity of the Optimal LLL Algorithm
Computability
Iteration Algebras Are Not Finitely Axiomatizable
Undecidable Problems in Unreliable Computations
Automata, Formal Languages
Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups
Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers
Unambiguous B\"{u}chi Automata
Linear Time Language Recognition on Cellular Automata with Restricted Communication
Logic, Programming Theory
From Semantics to Spatial Distribution
On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics
A Theory of Operational Equivalence for Interaction Nets
Analysis of Algorithms II
Run Statistics for Geometrically Distributed Random Variables
Generalized Covariances of Multi-dimensional Brownian Excursion Local Times
Combinatorics of Geometrically Distributed Random Variables: Length of Ascending Runs
Backmatter