Latin 2018: Theoretical Informatics: 13th Latin American Symposium, Buenos Aires, Argentina, April 16-19, 2018, Proceedings

ISBN-13: 9783319774039 / Angielski / Miękka / 2018 / 889 str.

Michael Bender; Martin Farach-Colton; Miguel A. Mosteiro

Spis treści

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.