José R. Correa / Alejandro Hevia / Marcos Kiwi (eds.)

Latin 2006 Theoretical Informatics

7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings
Herausgeber: Hevia, Alejandro, Kiwi, Marcos, Correa, José R.

• Broschiertes Buch

Produktbeschreibung

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.

---

Hinweis: Dieser Artikel kann nur an eine deutsche Lieferadresse ausgeliefert werden.

Produktdetails

• Lecture Notes in Computer Science 3887
• Verlag: Springer, Berlin
• Artikelnr. des Verlages: 11682462
• 2006. 2006
• Seitenzahl: 814
• Erscheinungstermin: 6. März 2006
• Englisch
• Abmessung: 238mm x 156mm x 45mm
• Gewicht: 1239g
• ISBN-13: 9783540327554
• ISBN-10: 354032755X
• Artikelnr.: 21014142

Autorenporträt

José R. Correa, Universidad Adolfo Ibánez, Santiago, Chile / Alejandro Hevia, Universidad de Chile, Santiago, Chile / Marcos Kiwi, Universidad de Chile, Santiago, Chile

Inhaltsangabe

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.
SharpEstimates 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.