LATIN 2016: Theoretical Informatics : 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings / edited by Evangelos Kranakis, Gonzalo Navarro, Edgar Chávez.

Format:

Book

Contributor:

Kranakis, Evangelos, editor.

Navarro, Gonzalo, editor.

Chávez, Edgar, editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

LNCS sublibrary. Theoretical computer science and general issues ; SL 1, 9644.

Theoretical Computer Science and General Issues ; 9644

Language:

English

Subjects (All):

Algorithms.

Computer science--Mathematics.

Computer science.

Computers.

Data structures (Computer science).

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Computation by Abstract Devices.

Data Structures.

Local Subjects:

Algorithm Analysis and Problem Complexity.

Discrete Mathematics in Computer Science.

Computation by Abstract Devices.

Data Structures.

Physical Description:

1 online resource (XXVI, 714 pages) : 114 illustrations.

Edition:

First edition 2016.

Contained In:

Springer eBooks

Place of Publication:

Berlin, Heidelberg : Springer Berlin Heidelberg : Imprint: Springer, 2016.

System Details:

text file PDF

Summary:

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, et cetera), 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 in Large 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.

Other Format:

Printed edition:

ISBN:

978-3-662-49529-2

9783662495292

Access Restriction:

Restricted for use by site license.