Full Description
This book constitutes the
refereed proceedings of the 12th Latin American Symposium on Theoretical
Informatics, LATIN 2016, held in Ensenada, Mexico, in April 2016.
The 52 papers presented
together with 5 abstracts were carefully reviewed and selected from 131
submissions. The papers address a variety of topics in theoretical computer
science with a certain focus on algorithms (approximation, online,
randomized, algorithmic game theory, etc.), analytic combinatorics and analysis
of algorithms, automata theory and formal languages, coding theory and data
compression, combinatorial algorithms, combinatorial optimization,
combinatorics and graph theory, complexity theory, computational algebra,
computational biology, computational geometry, computational number theory,
cryptology, databases and information retrieval, data structures, formal
methods and security, Internet and the web, parallel and distributed computing,
pattern matching, programming language theory, and random structures.
Contents
Reversible Figures and Solids.- Simplicity is in
Vogue (again).- Subgame Perfect Equilibrium: Computation and Efficiency.- Buying
Stuff Online.- Data Crowdsourcing: Is It for Real.- A Faster FPT Algorithm and
a Smaller Kernel for Block Graph Vertex Deletion.- A Middle Curve Based on
Discrete Fréchet Distance.- Comparison-Based FIFO Buffer Management in QoS
Switches.- Scheduling on Power-Heterogeneous Processors.- Period Recovery over
the Hamming and Edit Distances.- Chasing Convex Bodies and Functions.- Parameterized
Lower Bounds and Dichotomy Results for the NP-Completeness of H-Free Edge Modification
Problems.- Parameterized Complexity of Red Blue Set Cover for lines.- Tight
Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons.- On Mobile
Agent Verifiable Problems.- Computing Maximal Layers Of Points In Ef(n) .- On the Total Number
of Bends for Planar Octilinear Drawings.- Bidirectional BWT-Based De Bruijn
Graphs.- The Read/Write Protocol Complex is Collapsible.- The I/O Complexity of
Computing Prime Tables.-Increasing Diamonds.- Scheduling Transfers of Resources
over Time: Towards Car-Sharing with Flexible Drop-Offs.- A 0.821-Ratio Purely Combinatorial
Algorithm for Maximum k-Vertex Cover in Bipartite Graphs.- Improved Spanning
Ratio for Low Degree Spanners.- Constructing Consistent Digital Line Segments.-
Faster Information Gathering in Ad-Hoc Radio Tree Networks.- Stabbing circles
for Sets of Segments in the Plane.- Faster Algorithms to Enumerate Hypergraph
Transversals.- Listing Acyclic Orientations of Graphs with Single and Multiple
Sources.- Linear-Time Sequence Comparison Using Minimal Absent Words.- The
Grandmama de Bruijn Sequence for Binary Strings.- Compressing Bounded Degree Graphs.- Random Partial Match
Queries in Quad-K-d
Trees.- From Discrepancy to Majority.- On the Planar Split Thickness of
Graphs.- A Bounded-Risk Mechanism for the Kidney Exchange Game.- Tight
Approximations of Degeneracy inLarge Graphs.- Improved Approximation
Algorithms for Capacitated Fault-Tolerant k-Center.- Bundled Crossings in
Embedded Graphs.- Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin
Covering.- Deterministic Sparse Suffix Sorting on Rewritable Texts.- Minimizing
the Number of Opinions for Fault-Tolerant Distributed Decision Using Well-Quasi
Ordering.- Unshuffling Permutations.- Generating Random Spanning Trees via Fast
Matrix Multiplication.- Routing in Unit Disk Graphs.- Graph Drawings with One Bend
and Few Slopes.- Edge-Editing to a Dense and a Sparse Graph Class.- Containment
and Evasion in Stochastic Point Data.- Tree Compression Using String Grammars.-
Trees and Languages with Periodic Signature.- Rank Reduction of Directed Graphs
by Vertex and Edge Deletions.- New Deterministic Algorithms for Solving Parity
Games.- Computing a Geodesic Two-Center of Points in a Simple Polygon.- Simple
Approximation Algorithms for Balanced MAX 2SAT.- A Parameterized Algorithm for Mixed-Cut.- (k; n - k)-MAX-CUT: An O*(2p)-Time Algorithm and a Polynomial Kernel.- Independent
set of convex polygons: from nƐ to 1 + Ɛ via
shrinking.
