LATIN 2010: Theoretical Informatics: 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010. Proceedings

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 -