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

Front Cover
Springer Science & Business Media, Mar 6, 2006 - Computers - 814 pages

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.

 

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 Reflections 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
Reconfigurations 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 Efficient 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 Amplification Via SpaceEfficient 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
Author Index
812
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information