LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006. Proceedings

Ricardo Baeza-Yates (auth.), José R. Correa, Alejandro Hevia, Marcos Kiwi (eds.)354032755X, 9783540327554

This book constitutes the refereed proceedings of the 7th International Symposium, Latin American Theoretical Informatics, LATIN 2006, held in Valdivia, Chile in March 2006.

The 66 revised full papers presented together with seven invited papers were carefully reviewed and selected from 224 submissions. The papers presented are devoted to a broad range of topics in theoretical computer science with a certain focus on algorithmics and computations related to discrete mathematics as well as on cryptography, data compression and Web applications.

---

Table of contents :
Front Matter….Pages –
Algorithmic Challenges in Web Search Engines….Pages 1-7
RNA Molecules: Glimpses Through an Algorithmic Lens….Pages 8-10
Squares….Pages 11-12
Matching Based Augmentations for Approximating Connectivity Problems….Pages 13-24
Modelling Errors and Recovery for Communication….Pages 25-25
Lossless Data Compression Via Error Correction….Pages 26-27
The Power and Weakness of Randomness in Computation….Pages 28-29
A New GCD Algorithm for Quadratic Number Rings with Unique Factorization….Pages 30-42
On Clusters in Markov Chains….Pages 43-55
An Architecture for Provably Secure Computation….Pages 56-67
Scoring Matrices That Induce Metrics on Sequences….Pages 68-79
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams….Pages 80-92
The Complexity of Diffuse Reflections in a Simple Polygon….Pages 93-104
Counting Proportions of Sets: Expressive Power with Almost Order….Pages 105-117
Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets….Pages 118-129
Relations Among Notions of Security for Identity Based Encryption Schemes….Pages 130-141
Optimally Adaptive Integration of Univariate Lipschitz Functions….Pages 142-153
Classical Computability and Fuzzy Turing Machines….Pages 154-165
An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees….Pages 166-177
An Algorithm for a Generalized Maximum Subsequence Problem….Pages 178-189
Random Bichromatic Matchings….Pages 190-201
Eliminating Cycles in the Discrete Torus….Pages 202-210
On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions….Pages 211-223
Pattern Matching Statistics on Correlated Sources….Pages 224-237
Robust Model-Checking of Linear-Time Properties in Timed Automata….Pages 238-249
The Computational Complexity of the Parallel Knock-Out Problem….Pages 250-261
Reconfigurations in Graphs and Grids….Pages 262-273
${mathcal C}$ -Varieties, Actions and Wreath Product….Pages 274-285
Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges….Pages 286-297
An Efficient Approximation Algorithm for Point Pattern Matching Under Noise….Pages 298-310
Oblivious Medians Via Online Bidding….Pages 311-322
Efficient Computation of the Relative Entropy of Probabilistic Automata….Pages 323-336
A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences….Pages 337-348
De Dictionariis Dynamicis Pauco Spatio Utentibus….Pages 349-361
Customized Newspaper Broadcast: Data Broadcast with Dependencies….Pages 362-373
On Minimum k -Modal Partitions of Permutations….Pages 374-385
Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm….Pages 386-397
Maximizing Throughput in Queueing Networks with Limited Flexibility….Pages 398-409
Network Flow Spanners….Pages 410-422
Finding All Minimal Infrequent Multi-dimensional Intervals….Pages 423-434
Cut Problems in Graphs with a Budget Constraint….Pages 435-446
Lower Bounds for Clear Transmissions in Radio Networks….Pages 447-454
Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata….Pages 455-466
Lower Bounds for Geometric Diameter Problems….Pages 467-478
Connected Treewidth and Connected Graph Searching….Pages 479-490
A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs….Pages 491-501
The Committee Decision Problem….Pages 502-514
Common Deadline Lazy Bureaucrat Scheduling Revisited….Pages 515-523
Approximate Sorting….Pages 524-531
Stochastic Covering and Adaptivity….Pages 532-543
Algorithms for Modular Counting of Roots of Multivariate Polynomials….Pages 544-555
Hardness Amplification Via Space-Efficient Direct Products….Pages 556-568
The Online Freeze-Tag Problem….Pages 569-579
I/O-Efficient Algorithms on Near-Planar Graphs….Pages 580-591
Minimal Split Completions of Graphs….Pages 592-604
Design and Analysis of Online Batching Systems….Pages 605-616
Competitive Analysis of Scheduling Algorithms for Aggregated Links….Pages 617-628
A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains….Pages 629-640
On Sampling in Higher-Dimensional Peer-to-Peer Systems….Pages 641-652
Mobile Agent Rendezvous in a Synchronous Torus….Pages 653-664
Randomly Colouring Graphs with Girth Five and Large Maximum Degree….Pages 665-676
Packing Dicycle Covers in Planar Graphs with No K 5 – e Minor….Pages 677-688
Sharp Estimates for the Main Parameters of the Euclid Algorithm….Pages 689-702
Position-Restricted Substring Searching….Pages 703-714
Rectilinear Approximation of a Set of Points in the Plane….Pages 715-726
The Branch-Width of Circular-Arc Graphs….Pages 727-736
Minimal Eulerian Circuit in a Labeled Digraph….Pages 737-744
Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization….Pages 745-756
RISOTTO : Fast Extraction of Motifs with Mismatches….Pages 757-768
Minimum Cost Source Location Problems with Flow Requirements….Pages 769-780
Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms….Pages 781-792
Constructions of Approximately Mutually Unbiased Bases….Pages 793-799
Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In….Pages 800-811
Back Matter….Pages –