LATIN 2004LATIN 2004：理论信息学/会议录

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.

The LNCS series reports state-of-the-art results in computer science research，development，and education，at a high level and in both printed and electronic form. Enjoying tight cooperation with the R&D community，with numerous individuals，as well as with prestigious organizations and societies，LNCS has grown into the most comprehensive computer science research forum available.
The scope of LNCS，including its subseries LNAI，spans the whole range of computer science and information technology including interdisciplinary topics in a variety of application fields. The type of material published traditionally includes.
—proceedings （published in time for the respective conference）
—post-proceedings （consisting of thoroughly revised final full papers）
—research monographs（which may be based on outstanding PhD work，research projects，technical reports，etc.）

Invited Speakers
　Analysis of Scheduling Algorithms for Proportionate Fairness
　Advances in the Regularity Method
　Fighting Spare: 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 Aigorithms 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
……
Author Index