+612 9045 4394
Latin 2004: Theoretical Informatics : 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings - Martin Farach-Colton

Latin 2004: Theoretical Informatics

6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings

By: Martin Farach-Colton (Editor)

Paperback Published: 19th March 2004
ISBN: 9783540212584
Number Of Pages: 632

Share This Book:


or 4 easy payments of $45.31 with Learn more
Ships in 5 to 9 business days

This volume contains the proceedings of the Latin American Theoretical Inf- matics (LATIN) conference that was held in Buenos Aires, Argentina, April 5-8, 2004. The LATIN series of symposia was launched in 1992 to foster interactions between the Latin American community and computer scientists around the world. This was the sixth event in the series, following S~ ao Paulo, Brazil (1992), Valparaiso, Chile (1995), Campinas, Brazil (1998), Punta del Este, Uruguay (2000), and Cancun, Mexico (2002). The proceedings of these conferences were also published by Springer-Verlag in the Lecture Notes in Computer Science series: Volumes 583, 911, 1380, 1776, and 2286, respectively. Also, as before, we published a selection of the papers in a special issue of a prestigious journal. We received 178 submissions. Each paper was assigned to four program c- mittee members, and 59 papers were selected. This was 80% more than the previous record for the number of submissions. We feel lucky to have been able to build on the solid foundation provided by the increasingly successful previous LATINs. And we are very grateful for the tireless work of Pablo Mart´ ?nez L´ opez, the Local Arrangements Chair. Finally, we thank Springer-Verlag for publishing these proceedings in its LNCS series.

Analysis of scheduling algorithms for proportionate fairnessp. 1
Advances in the regularity methodp. 2
Fighting spam : the sciencep. 3
The consequences of Imre Simon's work in the theory of automata, languages, and semigroupsp. 5
Querying priced information in databases : the conjunctive casep. 6
Sublinear methods for detecting periodic trends in data streamsp. 16
An improved data stream summary : the count-min sketch and its applicationsp. 29
Rotation and lighting invariant template matchingp. 39
Computation of the bisection width for random d-regular graphsp. 49
Constrained integer partitionsp. 59
Embracing the giant componentp. 69
Sampling grid colorings with fewer colorsp. 80
The complexity of finding top-toda-equivalence-class membersp. 90
List partitions in chordal graphsp. 100
Bidimensional parameters and local treewidthp. 109
Vertex disjoint paths on clique-width bounded graphsp. 119
On partitioning interval and circular-arc graphs into proper interval subgraphs with applicationsp. 129
Collective tree explorationp. 141
Off-centers : a new type of steiner points for computing size-optimal quality-guaranteed delaunay triangulationsp. 152
Space-efficient algorithms for computing the convex hull of a simple polygonal line in linear timep. 162
A geometric approach to the bisection methodp. 172
Improved linear expected-time algorithms for computing maximap. 181
A constant approximation algorithm for sorting buffersp. 193
Approximation schemes for a class of subset selection problemsp. 203
Finding k-connected subgraphs with minimum average weightp. 212
On the (im)possibility of non-interactive correlation distillationp. 222
Pure future local temporal logics are expressively complete for Mazurkiewicz tracesp. 232
How expressions can code for automatap. 242
Automata for arithmetic meyer setsp. 252
Efficiently computing the density of regular languagesp. 262
Longest repeats with a book of don't caresp. 271
Join irreducible pseudovarieties, group mapping, and Kovacs-Newman semigroupsp. 279
Complementation of rational sets on scattered linear orderings of finite rankp. 292
Expected length for the longest common subsequence for large alphabetsp. 302
Universal types and simulation of individual sequencesp. 312
Separating codes : constructions and boundsp. 322
Encoding homotopy of paths in the planep. 329
A unified approach to coding labeled treesp. 339
Cost-optimal trees for ray shootingp. 349
Packing problems with orthogonal rotationsp. 359
Combinatorial problems on strings with applications to protein foldingp. 369
Measurement errors make the partial digest problem NP-hardp. 379
Designing small keyboards is hardp. 391
Metric structures in L[subscript 1] : dimension, snowflakes, and average distortionp. 401
Nash equilibria via polynomial equationsp. 413
Minimum latency tours and the k-traveling repairmen problemp. 423
Server scheduling in the weighted l[subscript p] normp. 434
An improved communication-randomness tradeoffp. 444
Distributed games and distributed control for asynchronous systemsp. 455
A simplified and dynamic unified structurep. 466
Another view of the Gaussian algorithmp. 474
Generating maximal independent sets for hypergraphs with bounded edge-intersectionsp. 488
Rooted maximum agreement supertreesp. 499
Complexity of cycle length modularity problems in graphsp. 509
Procedural semantics for fuzzy disjunctive programs on resituated latticesp. 519
A proof system and a decision procedure for equality logicp. 530
Approximating the expressive power of logics in finite modelsp. 540
Arithmetic circuits for discrete logarithmsp. 557
On the competitiveness of AIMD-TCP within a general networkp. 567
Gathering non-oblivious mobile robotsp. 577
Bisecting and gossiping in circulant graphsp. 589
Multiple mobile agent rendezvous in a ringp. 599
Global synchronization in sensornetsp. 609
Author indexp. 625
Table of Contents provided by Blackwell. All Rights Reserved.

ISBN: 9783540212584
ISBN-10: 3540212582
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 632
Published: 19th March 2004
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.39 x 15.6  x 3.3
Weight (kg): 0.89