## LATIN 2006: Theoretical Informatics: 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, ProceedingsThis 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Algorithmic Challenges in Web Search Engines | 1 |

Glimpses Through an Algorithmic Lens | 8 |

Squares | 11 |

Matching Based Augmentations for Approximating Connectivity Problems | 13 |

Modelling Errors and Recovery for Communication | 25 |

Lossless Data Compression Via Error Correction | 26 |

The Power and Weakness of Randomness in Computation | 28 |

On Clusters in Markov Chains | 43 |

The Best of Branchwidth and Treewidth with One Algorithm | 386 |

Maximizing Throughput in Queueing Networks with Limited Flexibility | 398 |

Network Flow Spanners | 410 |

Finding All Minimal Infrequent Multidimensional Intervals | 423 |

Cut Problems in Graphs with a Budget Constraint | 435 |

Lower Bounds for Clear Transmissions in Radio Networks | 447 |

Lower Bounds for Geometric Diameter Problems | 467 |

Connected Treewidth and Connected Graph Searching | 479 |

An Architecture for Provably Secure Computation | 56 |

Scoring Matrices That Induce Metrics on Sequences | 68 |

Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams | 80 |

The Complexity of Diffuse Reﬂections in a Simple Polygon | 93 |

Expressive Power with Almost Order | 105 |

Efficient Approximate Dictionary LookUp for Long Words over Small Alphabets | 118 |

Relations Among Notions of Security for Identity Based Encryption Schemes | 130 |

Optimally Adaptive Integration of Univariate Lipschitz Functions | 142 |

Classical Computability and Fuzzy Turing Machines | 154 |

An Optimal Algorithm for the ContinuousDiscrete Weighted 2Center Problem in Trees | 166 |

An Algorithm for a Generalized Maximum Subsequence Problem | 178 |

Random Bichromatic Matchings | 190 |

Eliminating Cycles in the Discrete Torus | 202 |

Bicriteria Mechanisms for UnitDemand Auctions | 211 |

Pattern Matching Statistics on Correlated Sources | 224 |

Robust ModelChecking of LinearTime Properties in Timed Automata | 238 |

The Computational Complexity of the Parallel KnockOut Problem | 250 |

Reconﬁgurations in Graphs and Grids | 262 |

CVarieties Actions and Wreath Product | 274 |

Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges | 286 |

An Efﬁcient Approximation Algorithm for Point Pattern Matching Under Noise | 298 |

Oblivious Medians Via Online Bidding | 311 |

Efficient Computation of the Relative Entropy of Probabilistic Automata | 323 |

A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences | 337 |

De Dictionariis Dynamicis Pauco Spatio Utentibus | 349 |

Data Broadcast with Dependencies | 362 |

On Minimum kModal Partitions of Permutations | 374 |

A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs | 491 |

The Committee Decision Problem | 502 |

Common Deadline Lazy Bureaucrat Scheduling Revisited | 515 |

Approximate Sorting | 524 |

Stochastic Covering and Adaptivity | 532 |

Algorithms for Modular Counting of Roots of Multivariate Polynomials | 544 |

Hardness Ampliﬁcation Via SpaceEfﬁcient Direct Products | 556 |

The Online FreezeTag Problem | 569 |

IOEfficient Algorithms on NearPlanar Graphs | 580 |

Minimal Split Completions of Graphs | 592 |

Design and Analysis of Online Batching Systems | 605 |

Competitive Analysis of Scheduling Algorithms for Aggregated Links | 617 |

A 4Approximation Algorithm for Guarding 15Dimensional Terrains | 629 |

On Sampling in HigherDimensional PeertoPeer Systems | 641 |

Mobile Agent Rendezvous in a Synchronous Torus | 653 |

Randomly Colouring Graphs with Girth Five and Large Maximum Degree | 665 |

Packing Dicycle Covers in Planar Graphs with No K5 e Minor | 677 |

in the Plane | 715 |

The BranchWidth of CircularArc Graphs | 727 |

Minimal Eulerian Circuit in a Labeled Digraph | 737 |

Spanning Forest Problems by Multiobjective Optimization | 745 |

Fast Extraction of Motifs with Mismatches | 757 |

Exponential Lower Bounds on the Space Complexity of OBDDBased Graph Algorithms | 781 |

Constructions of Approximately Mutually Unbiased Bases | 793 |

Improved ExponentialTime Algorithms for Treewidth and Minimum FillIn | 800 |

812 | |

### Other editions - View all

### Common terms and phrases

approximation algorithm assume automata automaton Berlin Heidelberg 2006 binary competitive ratio Computer Science conﬁguration connected components consider constant construction contains convex cost data structure deﬁned Deﬁnition degree denote deterministic deterministic algorithm diﬀerent dynamic edges eﬃcient elements ﬁnd ﬁnding ﬁnite ﬁrst ﬁxed ﬂow function given graph G Hevia input integer interval iteration J.R. Correa Kiwi Eds label least Lemma length linear LNCS lower bound Markov chain matching maximal cliques maximum metric minimal motif node NP-complete NP-hard O(log OBDD obtain online algorithm operation output pair partition path polynomial potential maximal cliques preﬁx Proof prove queries random robots satisﬁes schedule segment sequence server solution solve source location problems space spanning tree split graph subgraph subset subtree Theorem token torus tree-decomposition treewidth upper bound vector vertex vertices Voronoi diagram weight wreath product