LATIN 2022: Theoretical Informatics

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Cutting a Tree with Subgraph Complementation is Hard, Except for Some Small Trees
3. Altmetric Badge
   Chapter 2 Elastic-Degenerate String Matching with 1 Error
4. Altmetric Badge
   Chapter 3 Median and Hybrid Median K-Dimensional Trees
5. Altmetric Badge
   Chapter 4 Weighted Connected Matchings
6. Altmetric Badge
   Chapter 5 Space-Efficient Data Structure for Next/Previous Larger/Smaller Value Queries
7. Altmetric Badge
   Chapter 6 Near-Optimal Search Time in  $$\delta $$ δ -Optimal Space
8. Altmetric Badge
   Chapter 7 Computing and Listing Avoidable Vertices and Paths
9. Altmetric Badge
   Chapter 8 Klee’s Measure Problem Made Oblivious
10. Altmetric Badge
    Chapter 9 A Parameterized Approximation Algorithm for the Multiple Allocation k -Hub Center
11. Altmetric Badge
    Chapter 10 Theoretical Analysis of git bisect
12. Altmetric Badge
    Chapter 11 Pathlength of Outerplanar Graphs
13. Altmetric Badge
    Chapter 12 Approximations for the Steiner Multicycle Problem
14. Altmetric Badge
    Chapter 13 Approximation Schemes for Packing Problems with  $$\ell _p$$ ℓ p -norm Diversity Constraints
15. Altmetric Badge
    Chapter 14 Obtaining Approximately Optimal and Diverse Solutions via Dispersion
16. Altmetric Badge
    Chapter 15 On APN Functions Whose Graphs are Maximal Sidon Sets
17. Altmetric Badge
    Chapter 16 On the Subfield Codes of a Subclass of Optimal Cyclic Codes and Their Covering Structures
18. Altmetric Badge
    Chapter 17 Multidimensional Manhattan Preferences
19. Altmetric Badge
    Chapter 18 Exact Learning of Multitrees and Almost-Trees Using Path Queries
20. Altmetric Badge
    Chapter 19 Almost Optimal Proper Learning and Testing Polynomials
21. Altmetric Badge
    Chapter 20 Estimating the Clustering Coefficient Using Sample Complexity Analysis
22. Altmetric Badge
    Chapter 21 Binary Completely Reachable Automata
23. Altmetric Badge
    Chapter 22 Conelikes and Ranker Comparisons
24. Altmetric Badge
    Chapter 23 The Net Automaton of a Rational Expression
25. Altmetric Badge
    Chapter 24 Embedding Arbitrary Boolean Circuits into Fungal Automata
26. Altmetric Badge
    Chapter 25 How Many Times Do You Need to Go Back to the Future in Unary Temporal Logic?
27. Altmetric Badge
    Chapter 26 String Attractors and Infinite Words
28. Altmetric Badge
    Chapter 27 On the Zero-Sum Ramsey Problem over $$\mathbb {Z}_2^d$$
29. Altmetric Badge
    Chapter 28 On $$\chi $$-Diperfect Digraphs with Stability Number Two
30. Altmetric Badge
    Chapter 29 Percolation and Epidemic Processes in One-Dimensional Small-World Networks
31. Altmetric Badge
    Chapter 30 A Combinatorial Link Between Labelled Graphs and Increasingly Labelled Schröder Trees
32. Altmetric Badge
    Chapter 31 Min Orderings and List Homomorphism Dichotomies for Signed and Unsigned Graphs
33. Altmetric Badge
    Chapter 32 On the Zombie Number of Various Graph Classes
34. Altmetric Badge
    Chapter 33 Patterns in Ordered (random) Matchings
35. Altmetric Badge
    Chapter 34 Tree 3-Spanners on Generalized Prisms of Graphs
36. Altmetric Badge
    Chapter 35 A General Approach to Ammann Bars for Aperiodic Tilings
37. Altmetric Badge
    Chapter 36 List Homomorphism: Beyond the Known Boundaries
38. Altmetric Badge
    Chapter 37 On the Closures of Monotone Algebraic Classes and Variants of the Determinant
39. Altmetric Badge
    Chapter 38 MCSP is Hard for Read-Once Nondeterministic Branching Programs
40. Altmetric Badge
    Chapter 39 Bounds on Oblivious Multiparty Quantum Communication Complexity
41. Altmetric Badge
    Chapter 40 Improved Parallel Algorithms for Generalized Baumslag Groups
42. Altmetric Badge
    Chapter 41 Piercing Pairwise Intersecting Convex Shapes in the Plane
43. Altmetric Badge
    Chapter 42 Local Routing Algorithms on Euclidean Spanners with Small Diameter
44. Altmetric Badge
    Chapter 43 On r -Guarding SCOTs – A New Family of Orthogonal Polygons
45. Altmetric Badge
    Chapter 44 Complexity Results on Untangling Red-Blue Matchings
46. Altmetric Badge
    Chapter 45 On Vertex Guarding Staircase Polygons
47. Altmetric Badge
    Chapter 46 On the Complexity of Half-Guarding Monotone Polygons