附註:Includes bibliographical references and index.
Invited Speakers -- Analysis of Scheduling Algorithms for Proportionate Fairness -- Advances in the Regularity Method -- Fighting Spam: The Science -- The Consequences of Imre Simon's Work in the Theory of Automata, Languages, and Semigroups -- Contributions -- Querying Priced Information in Databases: The Conjunctive Case -- Sublinear Methods for Detecting Periodic Trends in Data Streams -- An Improved Data Stream Summary: The Count-Min Sketch and Its Applications -- Rotation and Lighting Invariant Template Matching -- Computation of the Bisection Width for Random d-Regular Graphs -- Constrained Integer Partitions -- Embracing the Giant Component -- Sampling Grid Colorings with Fewer Colors -- The Complexity of Finding Top-Toda-Equivalence-Class Members -- List Partitions of Chordal Graphs -- Bidimensional Parameters and Local Treewidth -- Vertex Disjoint Paths on Clique-Width Bounded Graphs -- On Partitioning Interval and Circular-Arc Graphs into Proper Interval Subgraphs with Applications -- Collective Tree Exploration -- Off-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations -- Space-Efficient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time -- A Geometric Approach to the Bisection Method -- Improved Linear Expected-Time Algorithms for Computing Maxima -- A Constant Approximation Algorithm for Sorting Buffers -- Approximation Schemes for a Class of Subset Selection Problems -- Finding k-Connected Subgraphs with Minimum Average Weight -- On the (Im)possibility of Non-interactive Correlation Distillation -- Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces -- How Expressions Can Code for Automata -- Automata for Arithmetic Meyer Sets -- Efficiently Computing the Density of Regular Languages -- Longest Repeats with a Block of Don't Cares -- Join Irreducible Pseudovarieties, Group Mapping, and Kovács-Newman Semigroups -- Complementation o
摘要:This book constitutes the refereed proceedings of the 6th International Symposium, Latin American Theoretical Informatics, LATIN 2004, held in Buenos Aires, Argentina, in April 2004. The 59 revised full papers presented were carefully reviewed and selected from 178 submissions. The papers presented are devoted to a broad range of topics in theoretical computer science with a certain focus on algorithmics and computations related to discrete mathematics.
