LATIN 2018: Theoretical Informatics : 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings / edited by Michael A. Bender, Martín Farach-Colton, Miguel A. Mosteiro.

Format:

Book

Contributor:

Bender, Michael A. (Computer scientist), editor.

Farach-Colton, Martin, editor.

Mosteiro, Miguel A., editor.

SpringerLink (Online service)

Series:

Computer Science (Springer-11645)

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

Theoretical Computer Science and General Issues ; 10807

Language:

English

Subjects (All):

Algorithms.

Computer organization.

Computer science--Mathematics.

Computer science.

Data structures (Computer science).

Computer graphics.

Artificial intelligence.

Algorithm Analysis and Problem Complexity.

Computer Systems Organization and Communication Networks.

Mathematics of Computing.

Data Structures.

Computer Graphics.

Artificial Intelligence.

Local Subjects:

Algorithm Analysis and Problem Complexity.

Computer Systems Organization and Communication Networks.

Mathematics of Computing.

Data Structures.

Computer Graphics.

Artificial Intelligence.

Physical Description:

1 online resource (XVII, 889 pages) : 142 illustrations.

Edition:

First edition 2018.

Contained In:

Springer eBooks

Place of Publication:

Cham : Springer International Publishing : Imprint: Springer, 2018.

System Details:

text file PDF

Summary:

This book constitutes the proceedings of the 13th Latin American Symposium on Theoretical Informatics, LATIN 2018, held in Buenos Aires, Argentina, in April 2018. The 63 papers presented in this volume were carefully reviewed and selected from 161 submissions. The Symposium is devoted to different areas in theoretical computer science, including, but not limited to: 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:

The graph tessellation cover number: extremal bounds, efficient algorithms and hardness

Approximate Correlation Clustering Using Same-Cluster Queries

Finding tight Hamilton cycles in random hypergraphs faster

Walking Through Waypoints

Lower Bounds for Online Matching on the Line

On the complexity of _nding internally vertex-disjoint long directed paths

Algorithms and Hardness Results for Nearest Neighbor Problems in Bicolored Point Sets

A Polynomial Sized Kernel for Tracking Paths Problem

Time-Space Trade-O_s for Computing Euclidean Minimum Spanning Trees

Approximate nearest neighbor for lp-spaces (2 < p < ) via embeddings

The Impact of Locality on the Detection of Cycles in the Broadcast Congested Clique Model

Partitioning Orthogonal Histograms into Rectangular Boxes

Compact Self-Stabilizing Leader Election for General Networks

Random Walks with Multiple Step Lengths

Tight Kernels for Covering and Hitting: Point Hyperplane Cover and Polynomial Point Hitting Set

A tight bound for shortest augmenting paths on trees

Approximation Algorithms for Replenishment Problems with Fixed Turnover Times

Maximum Box Problem on Stochastic Points

The Online Set Aggregation Problem

Agglomerative Clustering of Growing Squares

Fourier Entropy-Inuence Conjecture for Random Linear Threshold Functions

Property Suffix Array with Applications

Competitive Algorithms for Demand Response Management in Smart Grid

An Average-Case Lower Bound against ACC^0

Compressed Indexing with Signature Grammars

Combinatorics of Beacon-based Routing in Three Dimensions

On split B1-EPG graphs

Efficient algorithms for computing a minimal homology basis

Shifting the Phase Transition Threshold for Random Graphs using Degree Set Constraints

On the Biased Partial Word Collector Problem

Constructive Ramsey Numbers For Loose Hyperpaths

Cache Oblivious Sparse Matrix Multiplication

Don't Rock the Boat: Algorithms for Balanced Dynamic Loading and Unloading

Probabilistic Analysis of Online (Class-constrained) Bin Packing and Bin Covering

Locating the eigenvalues for graphs of small clique-width

On the Approximation Ratio of Lempel-Ziv Parsing

Kernelization for Maximum Happy Vertices Problem

When is Red-Blue Nonblocker FPT

Incremental Strong Connectivity and 2-Connectivity in Directed Graphs

Efficient Algorithms for Listing K Disjoint st-Paths in Graphs

Transversals of longest cycles in chordal and bounded tree-width graphs

Majority Model on Random Regular Graphs

Property testing for point sets on the plane

Maximal and Convex Layers of Random Point Sets

Plane Gossip: Approximating rumor spread in planar graphs

Algorithms and Bounds for Very Strong Rainbow Coloring

New Integer Linear Programming Models for the Vertex Coloring Problem

Submodular maximization with uncertain knapsack capacity

Select and Permute: An Improved Online Framework for Scheduling to Minimize Weighted Completion Time

Recognizing generalized transmission graphs of line segments and circular sectors

A Tight Lower Bound for an Online Hypercube Packing Problem and Bounds for Prices of Anarchy of a Related Game

The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue

Satisfying neighbor preferences on a circle

Two-dimensional Knapsack for Circles

Scheduling Parallelizable Jobs Online to Maximize Throughput

Reactive Proximity Data Structures for Graphs

Mutants and Residents with Different Connection Graphs in the Moran Process

A Framework for Algorithm Stability and its Application to Kinetic Euclidean MSTs

Rapid Mixing of k-Class Biased Permutations

Transition Operations over Plane Trees

Analysis of the Continued Logarithm Algorithm

Quadratic Simulations of Merlin-Arthur Games

On Counting Perfect Matchings in General Graphs.

Other Format:

Printed edition:

ISBN:

978-3-319-77404-6

9783319774046

Access Restriction:

Restricted for use by site license.