LATIN 2012: Theoretical Informatics: 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012. Proceedings

Front Matter....Pages -
A Generalization of the Convex Kakeya Problem....Pages 1-12
Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines....Pages 13-24
Bichromatic 2-Center of Pairs of Points....Pages 25-36
Erdős-Rényi Sequences and Deterministic Construction of Expanding Cayley Graphs....Pages 37-48
A Better Approximation Ratio and an IP Formulation for a Sensor Cover Problem....Pages 49-60
On the Advice Complexity of the Knapsack Problem....Pages 61-72
Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems....Pages 73-84
On Plane Constrained Bounded-Degree Spanners....Pages 85-96
Space-Efficient Approximation Scheme for Circular Earth Mover Distance....Pages 97-108
Density Classification on Infinite Lattices and Trees....Pages 109-120
Coloring Planar Homothets and Three-Dimensional Hypergraphs....Pages 121-132
An Equivariance Theorem with Applications to Renaming....Pages 133-144
Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks....Pages 145-156
Pseudorandomness of a Random Kronecker Sequence....Pages 157-171
Revisiting the Cache Miss Analysis of Multithreaded Algorithms....Pages 172-183
Parameterized Complexity of MaxSat above Average....Pages 184-194
Solving the 2-Disjoint Connected Subgraphs Problem Faster Than 2 n ....Pages 195-206
A O (1/ ε 2 ) n -Time Sieving Algorithm for Approximate Integer Programming....Pages 207-218
Two-Dimensional Range Diameter Queries....Pages 219-230
An Improved Upper Bound on the Density of Universal Random Graphs....Pages 231-242
Logspace Computations in Graph Groups and Coxeter Groups....Pages 243-254
Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points....Pages 255-266
On the Radon Number for P 3 -Convexity....Pages 267-278
Computing Minimum Geodetic Sets of Proper Interval Graphs....Pages 279-290
 Hausdorff Rank of Scattered Context-Free Linear Orders ....Pages 291-302
Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism....Pages 303-314
On the Non-progressive Spread of Influence through Social Networks....Pages 315-326
Forbidden Patterns....Pages 327-337
Structural Complexity of Multiobjective NP Search Problems....Pages 338-349
 k -Gap Interval Graphs....Pages 350-361
Decidability Classes for Mobile Agents Computing....Pages 362-374
NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets....Pages 375-386
Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width....Pages 387-398
Indexed Multi-pattern Matching....Pages 399-407
New Lower Bound on Max Cut of Hypergraphs with an Application to r -Set Splitting ....Pages 408-419
Cache Me If You Can: Capacitated Selfish Replication Games....Pages 420-432
The Efficiency of MapReduce in Parallel External Memory....Pages 433-445
Algorithms for Some H -Join Decompositions....Pages 446-457
On the Bend-Number of Planar and Outerplanar Graphs....Pages 458-469
Hiring above the m -th Best Candidate: A Generalization of Records in Permutations....Pages 470-481
On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost....Pages 482-493
Advantage of Overlapping Clusters for Minimizing Conductance....Pages 494-505
Independence of Tabulation-Based Hash Classes....Pages 506-517
Oblivious Two-Way Finite Automata: Decidability and Complexity....Pages 518-529
Clique-Colouring and Biclique-Colouring Unichord-Free Graphs....Pages 530-541
Random Walks and Bisections in Random Circulant Graphs....Pages 542-555
The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem....Pages 556-567
Fully Analyzing an Algebraic Pólya Urn Model....Pages 568-581
Degree-Constrained Node-Connectivity....Pages 582-593
Survivable Network Activation Problems....Pages 594-605
On the Integrality Gap of the Subtour LP for the 1,2-TSP....Pages 606-617
A Theory and Algorithms for Combinatorial Reoptimization....Pages 618-630
Capacity Achieving Two-Write WOM Codes....Pages 631-642
The Relationship between Inner Product and Counting Cycles....Pages 643-654
Approximating Minimum Label s - t Cut via Linear Programming....Pages 655-666
Back Matter....Pages -