LATIN 2016: Theoretical Informatics

12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings
Herausgegeben:Kranakis, Evangelos; Navarro, Gonzalo; Chávez, Edgar

• Broschiertes Buch

Produktbeschreibung

This book constitutes therefereed proceedings of the 12th Latin American Symposium on TheoreticalInformatics, LATIN 2016, held in Ensenada, Mexico, in April 2016.
The 52 papers presentedtogether with 5 abstracts were carefully reviewed and selected from 131submissions. The papers address a variety of topics in theoretical computerscience with a certain focus on algorithms (approximation, online,randomized, algorithmic game theory, etc.), analytic combinatorics and analysisof algorithms, automata theory and formal languages, coding theory and datacompression, 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, formalmethods and security, Internet and the web, parallel and distributed computing,pattern matching, programming language theory, and random structures.

Produktdetails

• Theoretical Computer Science and General Issues 9644
• Verlag: Springer / Springer Berlin Heidelberg / Springer, Berlin
• Artikelnr. des Verlages: 978-3-662-49528-5
• 1st ed. 2016
• Seitenzahl: 740
• Erscheinungstermin: 23. März 2016
• Englisch
• Abmessung: 235mm x 155mm x 40mm
• Gewicht: 1101g
• ISBN-13: 9783662495285
• ISBN-10: 3662495287
• Artikelnr.: 44492666

Inhaltsangabe

Reversible Figures and Solids.- Simplicity is inVogue (again).- Subgame Perfect Equilibrium: Computation and Efficiency.- BuyingStuff Online.- Data Crowdsourcing: Is It for Real.- A Faster FPT Algorithm anda Smaller Kernel for Block Graph Vertex Deletion.- A Middle Curve Based onDiscrete Fréchet Distance.- Comparison-Based FIFO Buffer Management in QoSSwitches.- Scheduling on Power-Heterogeneous Processors.- Period Recovery overthe Hamming and Edit Distances.- Chasing Convex Bodies and Functions.- ParameterizedLower Bounds and Dichotomy Results for the NP-Completeness of H-Free Edge ModificationProblems.- Parameterized Complexity of Red Blue Set Cover for lines.- TightBounds for Beacon-Based Coverage in Simple Rectilinear Polygons.- On MobileAgent Verifiable Problems.- Computing Maximal Layers Of Points In E^f(n) .- On the Total Numberof Bends for Planar Octilinear Drawings.- Bidirectional BWT-Based De BruijnGraphs.- The Read/Write Protocol Complex is Collapsible.- The I/O Complexity ofComputing Prime Tables.-Increasing Diamonds.- Scheduling Transfers of Resourcesover Time: Towards Car-Sharing with Flexible Drop-Offs.- A 0.821-Ratio Purely CombinatorialAlgorithm for Maximum k-Vertex Cover in Bipartite Graphs.- Improved SpanningRatio for Low Degree Spanners.- Constructing Consistent Digital Line Segments.-Faster Information Gathering in Ad-Hoc Radio Tree Networks.- Stabbing circlesfor Sets of Segments in the Plane.- Faster Algorithms to Enumerate HypergraphTransversals.- Listing Acyclic Orientations of Graphs with Single and MultipleSources.- Linear-Time Sequence Comparison Using Minimal Absent Words.- TheGrandmama de Bruijn Sequence for Binary Strings.- Compressing Bounded Degree Graphs.- Random Partial MatchQueries in Quad-K-dTrees.- From Discrepancy to Majority.- On the Planar Split Thickness ofGraphs.- A Bounded-Risk Mechanism for the Kidney Exchange Game.- TightApproximations of Degeneracy inLarge Graphs.- Improved ApproximationAlgorithms for Capacitated Fault-Tolerant k-Center.- Bundled Crossings inEmbedded Graphs.- Probabilistic Analysis of the Dual Next-Fit Algorithm for BinCovering.- Deterministic Sparse Suffix Sorting on Rewritable Texts.- Minimizingthe Number of Opinions for Fault-Tolerant Distributed Decision Using Well-QuasiOrdering.- Unshuffling Permutations.- Generating Random Spanning Trees via FastMatrix Multiplication.- Routing in Unit Disk Graphs.- Graph Drawings with One Bendand Few Slopes.- Edge-Editing to a Dense and a Sparse Graph Class.- Containmentand Evasion in Stochastic Point Data.- Tree Compression Using String Grammars.-Trees and Languages with Periodic Signature.- Rank Reduction of Directed Graphsby Vertex and Edge Deletions.- New Deterministic Algorithms for Solving ParityGames.- Computing a Geodesic Two-Center of Points in a Simple Polygon.- SimpleApproximation Algorithms for Balanced MAX 2SAT.- A Parameterized Algorithm for Mixed-Cut.- (k; n - k)-MAX-CUT: An O*(2^p)-Time Algorithm and a Polynomial Kernel.- Independentset of convex polygons: from n to 1 + viashrinking.