LATIN 2020: Theoretical Informatics

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 2 Near-Linear Time Algorithm for Approximate Minimum Degree Spanning Trees
3. Altmetric Badge
   Chapter 3 Approximation Algorithms for Cost-Robust Discrete Minimization Problems Based on Their LP-Relaxations
4. Altmetric Badge
   Chapter 4 Scheduling on Hybrid Platforms: Improved Approximability Window
5. Altmetric Badge
   Chapter 5 Leafy Spanning Arborescences in DAGs
6. Altmetric Badge
   Chapter 6 Approximating Routing and Connectivity Problems with Multiple Distances
7. Altmetric Badge
   Chapter 7 A 2-Approximation for the k -Prize-Collecting Steiner Tree Problem
8. Altmetric Badge
   Chapter 8 Maximizing Happiness in Graphs of Bounded Clique-Width
9. Altmetric Badge
   Chapter 9 Graph Hamiltonicity Parameterized by Proper Interval Deletion Set
10. Altmetric Badge
    Chapter 10 Graph Square Roots of Small Distance from Degree One Graphs
11. Altmetric Badge
    Chapter 11 Structural Parameterizations for Equitable Coloring
12. Altmetric Badge
    Chapter 12 Dynamically Optimal Self-adjusting Single-Source Tree Networks
13. Altmetric Badge
    Chapter 13 Batched Predecessor and Sorting with Size-Priced Information in External Memory
14. Altmetric Badge
    Chapter 14 Probabilistically Faulty Searching on a Half-Line
15. Altmetric Badge
    Chapter 16 Suffix Trees, DAWGs and CDAWGs for Forward and Backward Tries
16. Altmetric Badge
    Chapter 17 Towards a Definitive Measure of Repetitiveness
17. Altmetric Badge
    Chapter 18 Flips in Higher Order Delaunay Triangulations
18. Altmetric Badge
    Chapter 19 An $$\varOmega (n^3)$$ Ω ( n 3 ) Lower Bound on the Number of Cell Crossings for Weighted Shortest Paths in 3-Dimensional Polyhedral Structures
19. Altmetric Badge
    Chapter 20 Computing Balanced Convex Partitions of Lines
20. Altmetric Badge
    Chapter 21 Ordered Strip Packing
21. Altmetric Badge
    Chapter 22 Shortest Rectilinear Path Queries to Rectangles in a Rectangular Domain
22. Altmetric Badge
    Chapter 23 Farthest Color Voronoi Diagrams: Complexity and Algorithms
23. Altmetric Badge
    Chapter 24 Rectilinear Convex Hull of Points in 3D
24. Altmetric Badge
    Chapter 25 Monotone Circuit Lower Bounds from Robust Sunflowers
25. Altmetric Badge
    Chapter 26 Tight Bounds on Sensitivity and Block Sensitivity of Some Classes of Transitive Functions
26. Altmetric Badge
    Chapter 27 Sherali-Adams and the Binary Encoding of Combinatorial Principles
27. Altmetric Badge
    Chapter 28 Hardness of Variants of the Graph Coloring Game
28. Altmetric Badge
    Chapter 29 Tractable Unordered 3-CNF Games
29. Altmetric Badge
    Chapter 30 Lower Bounds for Testing Complete Positivity and Quantum Separability
30. Altmetric Badge
    Chapter 31 Exponential-Time Quantum Algorithms for Graph Coloring Problems
31. Altmetric Badge
    Chapter 32 On Symmetry and Initialization for Neural Networks
32. Altmetric Badge
    Chapter 33 How to Color a French Flag
33. Altmetric Badge
    Chapter 34 Simple Intrinsic Simulation of Cellular Automata in Oritatami Molecular Folding Model
34. Altmetric Badge
    Chapter 35 Transmitting once to Elect a Leader on Wireless Networks
35. Altmetric Badge
    Chapter 36 Asymptotics for Push on the Complete Graph
36. Altmetric Badge
    Chapter 37 The Hardness of Sampling Connected Subgraphs
37. Altmetric Badge
    Chapter 38 Lower Bounds for Max-Cut via Semidefinite Programming
38. Altmetric Badge
    Chapter 39 Quasi-Random Words and Limits of Word Sequences
39. Altmetric Badge
    Chapter 40 Thresholds in the Lattice of Subspaces of $$\mathbb {F}_q^n$$ F q n
40. Altmetric Badge
    Chapter 41 On Minimal-Perimeter Lattice Animals
41. Altmetric Badge
    Chapter 42 Improved Upper Bounds on the Growth Constants of Polyominoes and Polycubes
42. Altmetric Badge
    Chapter 43 On the Collection of Fringe Subtrees in Random Binary Trees
43. Altmetric Badge
    Chapter 44 A Method to Prove the Nonrationality of Some Combinatorial Generating Functions
44. Altmetric Badge
    Chapter 45 Binary Decision Diagrams: From Tree Compaction to Sampling
45. Altmetric Badge
    Chapter 46 Graph Sandwich Problem for the Property of Being Well-Covered and Partitionable into k Independent Sets and $$\ell $$ ℓ Cliques
46. Altmetric Badge
    Chapter 47 On the Maximum Number of Edges in Chordal Graphs of Bounded Degree and Matching Number
47. Altmetric Badge
    Chapter 49 On Some Subclasses of Split $$B_1$$ B 1 -EPG Graphs
48. Altmetric Badge
    Chapter 50 On the Helly Subclasses of Interval Bigraphs and Circular Arc Bigraphs