LATIN 2016: Theoretical Informatics: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings

Front Matter....Pages I-XXVI
A Middle Curve Based on Discrete Fréchet Distance....Pages 1-13
Comparison-Based FIFO Buffer Management in QoS Switches....Pages 14-26
Scheduling on Power-Heterogeneous Processors....Pages 27-40
Period Recovery over the Hamming and Edit Distances....Pages 41-54
Chasing Convex Bodies and Functions....Pages 55-67
Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of H-free Edge Modification Problems....Pages 68-81
Parameterized Complexity of Red Blue Set Cover for Lines....Pages 82-95
Tight Bounds for Beacon-Based Coverage in Simple Rectilinear Polygons....Pages 96-109
On Mobile Agent Verifiable Problems....Pages 110-122
On the Total Number of Bends for Planar Octilinear Drawings....Pages 123-137
Bidirectional Variable-Order de Bruijn Graphs....Pages 138-151
The Read/Write Protocol Complex Is Collapsible....Pages 152-163
The I/O Complexity of Computing Prime Tables....Pages 164-178
Increasing Diamonds....Pages 179-191
Scheduling Transfers of Resources over Time: Towards Car-Sharing with Flexible Drop-Offs....Pages 192-206
A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs....Pages 207-219
Improved Spanning Ratio for Low Degree Plane Spanners....Pages 220-234
Constructing Consistent Digital Line Segments....Pages 235-248
Faster Information Gathering in Ad-Hoc Radio Tree Networks....Pages 249-262
Stabbing Circles for Sets of Segments in the Plane....Pages 263-274
Faster Algorithms to Enumerate Hypergraph Transversals....Pages 275-289
Listing Acyclic Orientations of Graphs with Single and Multiple Sources....Pages 290-305
Linear-Time Sequence Comparison Using Minimal Absent Words & Applications....Pages 306-318
The Grandmama de Bruijn Sequence for Binary Strings....Pages 319-333
Compressing Bounded Degree Graphs....Pages 334-346
Random Partial Match in Quad-K-d Trees....Pages 347-361
From Discrepancy to Majority....Pages 362-375
On the Planar Split Thickness of Graphs....Pages 376-389
A Bounded-Risk Mechanism for the Kidney Exchange Game....Pages 390-402
Tight Approximations of Degeneracy in Large Graphs....Pages 403-415
Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center....Pages 416-428
Bundled Crossings in Embedded Graphs....Pages 429-440
Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering....Pages 441-453
Deterministic Sparse Suffix Sorting on Rewritable Texts....Pages 454-468
Minimizing the Number of Opinions for Fault-Tolerant Distributed Decision Using Well-Quasi Orderings....Pages 469-482
Unshuffling Permutations....Pages 483-496
Generating Random Spanning Trees via Fast Matrix Multiplication....Pages 497-508
Routing in Unit Disk Graphs....Pages 509-521
Graph Drawings with One Bend and Few Slopes....Pages 522-535
Edge-Editing to a Dense and a Sparse Graph Class....Pages 536-548
Containment and Evasion in Stochastic Point Data....Pages 549-561
Tree Compression Using String Grammars....Pages 562-575
Trees and Languages with Periodic Signature....Pages 576-589
Rank Reduction of Directed Graphs by Vertex and Edge Deletions....Pages 590-604
New Deterministic Algorithms for Solving Parity Games....Pages 605-618
Computing a Geodesic Two-Center of Points in a Simple Polygon....Pages 619-633
Simple Approximation Algorithms for Balanced MAX 2SAT....Pages 634-645
Back Matter....Pages 646-658
....Pages 659-671