## LATIN 2012: Theoretical Informatics: 10th Latin American Symposium, Arequipa, Peru, April 16-20, 2012, ProceedingsThis book constitutes the proceedings of the 10th Latin American Symposium on Theoretical Informatics, LATIN 2012, held in Arequipa, Peru, in April 2012. The 55 papers presented in this volume were carefully reviewed and selected from 153 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

A Generalization of the Convex Kakeya Problem
| 1 |

Low Complexity Scheduling Algorithm Minimizing the Energy for Tasks with Agreeable Deadlines
| 13 |

Bichromatic 2Center of Pairs of Points | 25 |

ErdosRenyi Sequences and Deterministic Construction of Expanding Cayley Graphs
| 37 |

A Better Approximation Ratio and an IP Formulation for a Sensor Cover Problem
| 49 |

On the Advice Complexity of the Knapsack Problem
| 61 |

Reoptimization of Some Maximum Weight Induced Hereditary Subgraph Problems
| 73 |

On Plane Constrained BoundedDegree Spanners
| 85 |

kGap Interval Graphs | 350 |

Decidability Classes for Mobile Agents Computing
| 362 |

NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets
| 375 |

Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted TreeWidth
| 387 |

Indexed Multipattern Matching | 399 |

New Lower Bound on Max Cut of Hypergraphs with an Application to rSet Splitting
| 408 |

Capacitated Selfish Replication Games
| 420 |

The Efficiency of MapReduce in Parallel External Memory
| 433 |

SpaceEfficient Approximation Scheme for Circular Earth Mover Distance
| 97 |

Density Classification on Infinite Lattices and Trees
| 109 |

Coloring Planar Homothets and ThreeDimensional Hypergraphs
| 121 |

An Equivariance Theorem with Applications to Renaming
| 133 |

A Map of Subconsensus Tasks
| 145 |

Pseudorandomness of a Random Kronecker Sequence
| 157 |

Revisiting the Cache Miss Analysis of Multithreaded Algorithms
| 172 |

Parameterized Complexity of MaxSat above Average
| 184 |

Solving the 2Disjoint Connected Subgraphs Problem Faster Than 2n
| 195 |

A O1 2nTime Sieving Algorithm for Approximate Integer Programming
| 207 |

TwoDimensional Range Diameter Queries | 219 |

An Improved Upper Bound on the Density of Universal Random Graphs
| 231 |

Logspace Computations in Graph Groups and Coxeter Groups
| 243 |

Approximating the Edge Length of 2Edge Connected Planar Geometric Graphs on a Set of Points
| 255 |

On the Radon Number for P3Convexity | 267 |

Computing Minimum Geodetic Sets of Proper Interval Graphs
| 279 |

Hausdorff Rank of Scattered ContextFree Linear Orders
| 291 |

Adaptiveness vs Obliviousness and Randomization vs
Determinism | 303 |

On the Nonprogressive Spread of Influence through Social Networks
| 315 |

Forbidden Patterns | 327 |

Structural Complexity of Multiobjective NP Search Problems
| 338 |

Algorithms for Some HJoin Decompositions | 446 |

On the BendNumber of Planar and Outerplanar Graphs
| 458 |

A Generalization of Records in Permutations
| 470 |

On the Performance of Smiths Rule in SingleMachine Scheduling with Nonlinear Cost
| 482 |

Advantage of Overlapping Clustersfor Minimizing Conductance | 494 |

Independence of TabulationBased Hash Classes | 506 |

Decidability and Complexity
| 518 |

CliqueColouring and BicliqueColouring UnichordFree Graphs
| 530 |

Random Walks and Bisections in Random Circulant Graphs
| 542 |

The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem
| 556 |

Fully Analyzing an Algebraic Polya Urn Model | 568 |

DegreeConstrained NodeConnectivity | 582 |

Survivable Network Activation Problems | 594 |

On the Integrality Gap of the Subtour LP for the 12TSP
| 606 |

A Theory and Algorithms for Combinatorial Reoptimization
| 618 |

Capacity Achieving TwoWrite WOM Codes | 631 |

The Relationship between Inner Product and Counting Cycles
| 643 |

Approximating Minimum Label st Cut via Linear Programming
| 655 |

667 | |

### Other editions - View all

### Common terms and phrases

2DFA anti-Radon set approximation algorithm assume Berlin Heidelberg 2012 biclique-colouring bipartite cache circulant graphs clauses clique clustering colors complexity Computer Science cone connected consider constraints construction contains convex Coxeter groups cycle deﬁne defined denote deterministic disjoint edge exists Fernández-Baca finite fixed-parameter tractable geodetic given graph G hash Heidelberg Hence homogeneous pair hyperedges hypergraph independent input instance integer integrality gap intersection interval graphs Label s-t Cut Lemma LNCS logn logspace lower bound MapReduce networks node NP-hard O(log obtain online algorithm output parameter parameterized parameterized complexity partition path planar planar graph polynomial problem processor proof protocol prove queries random ratio reduce reoptimization s-t Cut satisfies schedule sensor sequence solve Springer subgraph subset subtour LP task Theorem tree triangle undirected undirected graphs unichord-free graph upper bound variables vector vertex vertices weight