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.
Author(s): Cristopher Moore (auth.), Alejandro López-Ortiz (eds.)
Series: Lecture Notes in Computer Science 6034 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2010
Language: English
Pages: 706
Tags: Algorithm Analysis and Problem Complexity; Artificial Intelligence (incl. Robotics); Discrete Mathematics in Computer Science; Computer Communication Networks; Computation by Abstract Devices; Information Systems Applications (incl.Inter
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 -
