LATIN 2010: Theoretical Informatics: 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010, Proceedings (Lecture Notes in Computer Science, 6034)

This book constitutes the refereed proceedings of the 9th International Latin American Symposium on Theoretical Informatics, LATIN 2010, held in Oaxaca, Mexico; in April 2010. The 56 revised full papers presented together with the abstracts of 4 invited plenary talks were carefully reviewed and selected from 155 submissions. The papers address a variety of topics in theoretical computer science with a certain focus on algorithms, automata theory and formal languages, coding theory and data compression, algorithmic graph theory and combinatorics, complexity theory, computational algebra, computational biology, computational geometry, computational number theory, cryptography, theoretical aspects of databases and information retrieval, data structures, networks, logic in computer science, machine learning, mathematical programming, parallel and distributed computing, pattern matching, quantum computing and random structures. Front Matter....Pages - Continuous and Discrete Methods in Computer Science....Pages 1-1 Colorful Strips....Pages 2-13 The Mono- and Bichromatic Empty Rectangle and Square Problems in All Dimensions....Pages 14-25 Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Set....Pages 26-37 Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machines....Pages 38-48 Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Width....Pages 49-59 Average Parameterization and Partial Kernelization for Computing Medians....Pages 60-71 Sharp Separation and Applications to Exact and Parameterized Algorithms....Pages 72-83 Finding the Minimum-Distance Schedule for a Boundary Searcher with a Flashlight....Pages 84-95 The Language Theory of Bounded Context-Switching....Pages 96-107 Local Search Performance Guarantees for Restricted Related Parallel Machine Scheduling....Pages 108-119 Packet Routing on the Grid....Pages 120-130 Faithful Representations of Graphs by Islands in the Extended Grid....Pages 131-142 The I/O Complexity of Sparse Matrix Dense Matrix Multiplication....Pages 143-156 Sparse Recovery Using Sparse Random Matrices....Pages 157-157 Optimal Succinctness for Range Minimum Queries....Pages 158-169 Compact Rich-Functional Binary Relation Representations....Pages 170-183 Radix Cross-Sections for Length Morphisms....Pages 184-195 Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata....Pages 196-207 Quotient Complexity of Ideal Languages....Pages 208-221 Complexity of Operations on Cofinite Languages....Pages 222-233 Fast Set Intersection and Two-Patterns Matching....Pages 234-242 Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields....Pages 243-254 A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplication....Pages 255-266 Modelling the LLL Algorithm by Sandpiles....Pages 267-281 Communication-Efficient Construction of the Plane Localized Delaunay Graph....Pages 282-293 Time Complexity of Distributed Topological Self-stabilization: The Case of Graph Linearization....Pages 294-305 Randomised Broadcasting: Memory vs. Randomness....Pages 306-319 Limit Theorems for Random MAX-2-XORSAT....Pages 320-331 On Quadratic Threshold CSPs....Pages 332-343 Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming....Pages 344-355 Finding the Best CAFE Is NP-Hard....Pages 356-371 The Size and Depth of Layered Boolean Circuits....Pages 372-383 Lipschitz Unimodal and Isotonic Regression on Paths and Trees....Pages 384-396 Ambiguity and Deficiency in Costas Arrays and APN Permutations....Pages 397-406 Iterated Shared Memory Models....Pages 407-416 Optimal Polygonal Representation of Planar Graphs....Pages 417-432 Minimum-Perimeter Intersecting Polygons....Pages 433-445 Finding the Smallest Gap between Sums of Square Roots....Pages 446-455 Matching Points with Things....Pages 456-467 Homotopic Rectilinear Routing with Few Links and Thick Edges....Pages 468-479 Tilings Robust to Errors....Pages 480-491 Visiting a Sequence of Points with a Bevel-Tip Needle....Pages 492-502 Euclidean Prize-Collecting Steiner Forest....Pages 503-514 Prize-Collecting Steiner Networks via Iterative Rounding....Pages 515-526 Kernelization through Tidying....Pages 527-538 Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomials....Pages 539-553 The Power of Fair Pricing Mechanisms....Pages 554-564 Quasi-Proportional Mechanisms: Prior-Free Revenue Maximization....Pages 565-576 Some Observations on Holographic Algorithms....Pages 577-590 The Interval Constrained 3-Coloring Problem....Pages 591-602 Counting Hexagonal Patches and Independent Sets in Circle Graphs....Pages 603-614 Approximating Maximum Diameter-Bounded Subgraphs....Pages 615-626 Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentration....Pages 627-637 The Complexity of Counting Eulerian Tours in 4-Regular Graphs....Pages 638-649 Efficient Edge Domination on Hole-Free Graphs in Polynomial Time....Pages 650-661 Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs....Pages 662-673 Rank Selection in Multidimensional Data....Pages 674-685 Layered Working-Set Trees....Pages 686-696 Lightweight Data Indexing and Compression in External Memory....Pages 697-710 Back Matter....Pages -