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

ISBN-13: 9783540327554 / Angielski / Miękka / 2006 / 814 str.

Josi R. Correa

Opis

This book constitutes the refereed proceedings of the 7th International Symposium, Latin American Theoretical Informatics, LATIN 2006, held 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 focus on algorithmics and computations related to discrete mathematics as well as on cryptography, data compression and Web applications.

Spis treści

Keynotes.- Algorithmic Challenges in Web Search Engines.- RNA Molecules: Glimpses Through an Algorithmic Lens.- Squares.- Matching Based Augmentations for Approximating Connectivity Problems.- Modelling Errors and Recovery for Communication.- Lossless Data Compression Via Error Correction.- The Power and Weakness of Randomness in Computation.- Regular Contributions.- A New GCD Algorithm for Quadratic Number Rings with Unique Factorization.- On Clusters in Markov Chains.- An Architecture for Provably Secure Computation.- Scoring Matrices That Induce Metrics on Sequences.- Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams.- The Complexity of Diffuse Reflections in a Simple Polygon.- Counting Proportions of Sets: Expressive Power with Almost Order.- Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets.- Relations Among Notions of Security for Identity Based Encryption Schemes.- Optimally Adaptive Integration of Univariate Lipschitz Functions.- Classical Computability and Fuzzy Turing Machines.- An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees.- An Algorithm for a Generalized Maximum Subsequence Problem.- Random Bichromatic Matchings.- Eliminating Cycles in the Discrete Torus.- On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions.- Pattern Matching Statistics on Correlated Sources.- Robust Model-Checking of Linear-Time Properties in Timed Automata.- The Computational Complexity of the Parallel Knock-Out Problem.- Reconfigurations in Graphs and Grids.- -Varieties, Actions and Wreath Product.- Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges.- An Efficient Approximation Algorithm for Point Pattern Matching Under Noise.- Oblivious Medians Via Online Bidding.- Efficient Computation of the Relative Entropy of Probabilistic Automata.- A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences.- De Dictionariis Dynamicis Pauco Spatio Utentibus.- Customized Newspaper Broadcast: Data Broadcast with Dependencies.- On Minimum k-Modal Partitions of Permutations.- Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm.- Maximizing Throughput in Queueing Networks with Limited Flexibility.- Network Flow Spanners.- Finding All Minimal Infrequent Multi-dimensional Intervals.- Cut Problems in Graphs with a Budget Constraint.- Lower Bounds for Clear Transmissions in Radio Networks.- Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata.- Lower Bounds for Geometric Diameter Problems.- Connected Treewidth and Connected Graph Searching.- A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs.- The Committee Decision Problem.- Common Deadline Lazy Bureaucrat Scheduling Revisited.- Approximate Sorting.- Stochastic Covering and Adaptivity.- Algorithms for Modular Counting of Roots of Multivariate Polynomials.- Hardness Amplification Via Space-Efficient Direct Products.- The Online Freeze-Tag Problem.- I/O-Efficient Algorithms on Near-Planar Graphs.- Minimal Split Completions of Graphs.- Design and Analysis of Online Batching Systems.- Competitive Analysis of Scheduling Algorithms for Aggregated Links.- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains.- On Sampling in Higher-Dimensional Peer-to-Peer Systems.- Mobile Agent Rendezvous in a Synchronous Torus.- Randomly Colouring Graphs with Girth Five and Large Maximum Degree.- Packing Dicycle Covers in Planar Graphs with No K 5–e Minor.- Sharp Estimates for the Main Parameters of the Euclid Algorithm.- Position-Restricted Substring Searching.- Rectilinear Approximation of a Set of Points in the Plane.- The Branch-Width of Circular-Arc Graphs.- Minimal Eulerian Circuit in a Labeled Digraph.- Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization.- RISOTTO: Fast Extraction of Motifs with Mismatches.- Minimum Cost Source Location Problems with Flow Requirements.- Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms.- Constructions of Approximately Mutually Unbiased Bases.- Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In.