LATIN 2004: Theoretical Informatics

Table of Contents

1. Altmetric Badge
   Book Overview
2. Altmetric Badge
   Chapter 1 Analysis of Scheduling Algorithms for Proportionate Fairness
3. Altmetric Badge
   Chapter 2 Advances in the Regularity Method
4. Altmetric Badge
   Chapter 3 Fighting Spam: The Science
5. Altmetric Badge
   Chapter 4 The Consequences of Imre Simon’s Work in the Theory of Automata, Languages, and Semigroups
6. Altmetric Badge
   Chapter 5 Querying Priced Information in Databases: The Conjunctive Case
7. Altmetric Badge
   Chapter 6 Sublinear Methods for Detecting Periodic Trends in Data Streams
8. Altmetric Badge
   Chapter 7 An Improved Data Stream Summary: The Count-Min Sketch and Its Applications
9. Altmetric Badge
   Chapter 8 Rotation and Lighting Invariant Template Matching
10. Altmetric Badge
    Chapter 9 Computation of the Bisection Width for Random d-Regular Graphs
11. Altmetric Badge
    Chapter 10 Constrained Integer Partitions
12. Altmetric Badge
    Chapter 11 Embracing the Giant Component
13. Altmetric Badge
    Chapter 12 Sampling Grid Colorings with Fewer Colors
14. Altmetric Badge
    Chapter 13 The Complexity of Finding Top-Toda-Equivalence-Class Members
15. Altmetric Badge
    Chapter 14 List Partitions of Chordal Graphs
16. Altmetric Badge
    Chapter 15 Bidimensional Parameters and Local Treewidth
17. Altmetric Badge
    Chapter 16 Vertex Disjoint Paths on Clique-Width Bounded Graphs
18. Altmetric Badge
    Chapter 17 On Partitioning Interval and Circular-Arc Graphs into Proper Interval Subgraphs with Applications
19. Altmetric Badge
    Chapter 18 Collective Tree Exploration
20. Altmetric Badge
    Chapter 19 Off-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations
21. Altmetric Badge
    Chapter 20 Space-Efficient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time
22. Altmetric Badge
    Chapter 21 A Geometric Approach to the Bisection Method
23. Altmetric Badge
    Chapter 22 Improved Linear Expected-Time Algorithms for Computing Maxima
24. Altmetric Badge
    Chapter 23 A Constant Approximation Algorithm for Sorting Buffers
25. Altmetric Badge
    Chapter 24 Approximation Schemes for a Class of Subset Selection Problems
26. Altmetric Badge
    Chapter 25 Finding k -Connected Subgraphs with Minimum Average Weight
27. Altmetric Badge
    Chapter 26 On the (Im)possibility of Non-interactive Correlation Distillation
28. Altmetric Badge
    Chapter 27 Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces
29. Altmetric Badge
    Chapter 28 How Expressions Can Code for Automata
30. Altmetric Badge
    Chapter 29 Automata for Arithmetic Meyer Sets
31. Altmetric Badge
    Chapter 30 Efficiently Computing the Density of Regular Languages
32. Altmetric Badge
    Chapter 31 Longest Repeats with a Block of Don’t Cares
33. Altmetric Badge
    Chapter 32 Join Irreducible Pseudovarieties, Group Mapping, and Kovács-Newman Semigroups
34. Altmetric Badge
    Chapter 33 Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank
35. Altmetric Badge
    Chapter 34 Expected Length of the Longest Common Subsequence for Large Alphabets
36. Altmetric Badge
    Chapter 35 Universal Types and Simulation of Individual Sequences
37. Altmetric Badge
    Chapter 36 Separating Codes: Constructions and Bounds
38. Altmetric Badge
    Chapter 37 Encoding Homotopy of Paths in the Plane
39. Altmetric Badge
    Chapter 38 A Unified Approach to Coding Labeled Trees
40. Altmetric Badge
    Chapter 39 Cost-Optimal Trees for Ray Shooting
41. Altmetric Badge
    Chapter 40 Packing Problems with Orthogonal Rotations
42. Altmetric Badge
    Chapter 41 Combinatorial Problems on Strings with Applications to Protein Folding
43. Altmetric Badge
    Chapter 42 Measurement Errors Make the Partial Digest Problem NP -Hard
44. Altmetric Badge
    Chapter 43 Designing Small Keyboards Is Hard
45. Altmetric Badge
    Chapter 44 Metric Structures in L 1 : Dimension, Snowflakes, and Average Distortion
46. Altmetric Badge
    Chapter 45 Nash Equilibria via Polynomial Equations
47. Altmetric Badge
    Chapter 46 Minimum Latency Tours and the k -Traveling Repairmen Problem
48. Altmetric Badge
    Chapter 47 Server Scheduling in the Weighted ℓ p Norm
49. Altmetric Badge
    Chapter 48 An Improved Communication-Randomness Tradeoff
50. Altmetric Badge
    Chapter 49 Distributed Games and Distributed Control for Asynchronous Systems
51. Altmetric Badge
    Chapter 50 A Simplified and Dynamic Unified Structure
52. Altmetric Badge
    Chapter 51 Another View of the Gaussian Algorithm
53. Altmetric Badge
    Chapter 52 Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections
54. Altmetric Badge
    Chapter 53 Rooted Maximum Agreement Supertrees
55. Altmetric Badge
    Chapter 54 Complexity of Cycle Length Modularity Problems in Graphs
56. Altmetric Badge
    Chapter 55 Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices
57. Altmetric Badge
    Chapter 56 A Proof System and a Decision Procedure for Equality Logic
58. Altmetric Badge
    Chapter 57 Approximating the Expressive Power of Logics in Finite Models
59. Altmetric Badge
    Chapter 58 Arithmetic Circuits for Discrete Logarithms
60. Altmetric Badge
    Chapter 59 On the Competitiveness of AIMD-TCP within a General Network
61. Altmetric Badge
    Chapter 60 Gathering Non-oblivious Mobile Robots
62. Altmetric Badge
    Chapter 61 Bisecting and Gossiping in Circulant Graphs
63. Altmetric Badge
    Chapter 62 Multiple Mobile Agent Rendezvous in a Ring
64. Altmetric Badge
    Chapter 63 Global Synchronization in Sensornets