LATIN 2000: Theoretical Informatics: 4th Latin American Symposium, Punta del Esk, Uruguay, April 10-14, 2000 Proceedings

Front Matter....Pages -
Algorithmic Aspects of Regularity....Pages 1-17
Small Maximal Matchings in Random Graphs....Pages 18-27
Some Remarks on Sparsely Connected Isomorphism-Free Labeled Graphs....Pages 28-37
Analysis of Edge Deletion Processes on Faulty Random Regular Graphs....Pages 38-47
Equivalent Conditions for Regularity  (Extended Abstract)....Pages 48-57
Cube Packing....Pages 58-67
Approximation Algorithms for Flexible Job Shop Problems....Pages 68-77
Emerging Behavior as Binary Search Trees Are Symmetrically Updated....Pages 78-87
The LCA Problem Revisited....Pages 88-94
Optimal and Pessimal Orderings of Steiner Triple Systems in Disk Arrays....Pages 95-104
Rank Inequalities for Packing Designs and Sparse Triple Systems....Pages 105-114
The Anti-Oberwolfach Solution: Pancyclic 2-Factorizations of Complete Graphs....Pages 115-122
Graph Structure of the Web: A Survey....Pages 123-125
Polynomial Time Recognition of Clique-Width ≤  3 Graphs....Pages 126-134
On Dart-Free Perfectly Contractile Graphs Extended Abstract....Pages 135-144
Edge Colouring Reduced Indifference Graphs....Pages 145-153
Two Conjectures on the Chromatic Polynomial....Pages 154-162
Finding Skew Partitions Efficiently....Pages 163-172
On the Competitive Theory and Practice of Portfolio Selection (Extended Abstract)....Pages 173-196
Almost k -Wise Independence and Hard Boolean Functions....Pages 197-206
Improved Upper Bounds on the Simultaneous Messages Complexity of the Generalized Addressing Function....Pages 207-216
Multi-parameter Minimum Spanning Trees....Pages 217-226
Linear Time Recognition of Optimal L-Restricted Prefix Codes....Pages 227-236
Uniform Multi-hop All-to-All Optical Routings in Rings....Pages 237-246
A Fully Dynamic Algorithm for Distributed Shortest Paths....Pages 247-257
Integer Factorization and Discrete Logarithms....Pages 258-258
Communication Complexity and Fourier Coefficients of the Diffie–Hellman Key....Pages 259-268
Quintic Reciprocity and Primality Test for Numbers of the Form $M~=~A5^{n} \pm ~\omega_{n}$ ....Pages 269-279
Determining the Optimal Contrast for Secret Sharing Schemes in Visual Cryptography....Pages 280-291
Average-Case Analysis of Rectangle Packings....Pages 292-297
Heights in Generalized Tries and PATRICIA Tries....Pages 298-307
On the Complexity of Routing Permutations on Trees by Arc-Disjoint Paths Extended Abstract....Pages 308-317
Subresultants Revisited....Pages 318-342
A Unifying Framework for the Analysis of a Class of Euclidean Algorithms....Pages 343-354
Worst-Case Complexity of the Optimal LLL Algorithm....Pages 355-366
Iteration Algebras Are Not Finitely Axiomatizable....Pages 367-376
Undecidable Problems in Unreliable Computations....Pages 377-386
Equations in Free Semigroups with Anti-involution and Their Relation to Equations in Free Groups....Pages 387-396
Squaring Transducers: An Efficient Procedure for Deciding Functionality and Sequentiality of Transducers....Pages 397-406
Unambiguous Büchi Automata....Pages 407-416
Linear Time Language Recognition on Cellular Automata with Restricted Communication....Pages 417-426
From Semantics to Spatial Distribution....Pages 427-436
On the Expressivity and Complexity of Quantitative Branching-Time Temporal Logics....Pages 437-446
A Theory of Operational Equivalence for Interaction Nets....Pages 447-456
Run Statistics for Geometrically Distributed Random Variables....Pages 457-462
Generalized Covariances of Multi-dimensional Brownian Excursion Local Times....Pages 463-472
Combinatorics of Geometrically Distributed Random Variables: Length of Ascending Runs....Pages 473-482
Back Matter....Pages -