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

Front Cover
David Fernández-Baca
Springer Science & Business Media, Mar 30, 2012 - Computers - 669 pages
This 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
Author Index
667
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information