+612 9045 4394
Latin 2010: Theoretical Informatics : 9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010, Proceedings - Alejandro Lopez-Ortiz

Latin 2010: Theoretical Informatics

9th Latin American Symposium, Oaxaca, Mexico, April 19-23, 2010, Proceedings

By: Alejandro Lopez-Ortiz (Editor)


Published: 9th April 2010
Ships: 15 business days
15 business days
or 4 easy payments of $53.31 with Learn more

The papers contained in this volume were presented at the 9th Latin American TheoreticalInformaticsSymposiumheldattheBenitoJu' arezUniversityofO- aca, Oaxaca City, M' exico, April 19-23, 2010. The LATIN series of conferences was launched in 1992 to foster the interaction between the Latin American t- oretical computer science community and computer scientists around the world. LATIN 2010wasthe ninth ofa series,after SaoPaulo,Brazil(1992);Valparaiso, Chile (1995); Campinas, Brazil (1998); Punta del Este, Uruguay (2000); C- cun, Mexico (2002); Buenos Aires, Argentina (2004); Valdivia, Chile (2006) and B' uzios, Rio de Janeiro, Brazil (2008). From the 155 submissions, the Program Committee selected 56 papers for presentation at the conference. The selectionofpaperswasbasedonoriginality, quality, and relevance to theoretical computer science. It is expected that most of these papers will appear in a more complete and polished form in scienti?c journalsinthefuture.Inadditiontothecontributedpapers,thisvolumecontains the abstracts of four invited plenary talks given at the conference by Cristopher Moore, Piotr Indyk, Sergio Rajsbaum, and Leslie Valiant. A special session on the life and work of the late Imre Simon was held. Prof. Simon played a key role in the development of theoretical computer science in Latin American as well as theLATINconference.ThissessionhadcontributionsfromRicardoBaeza-Yates, John Brzozowski, Volker Diekert, and Jacques Sakarovitch.

Continuous and Discrete Methods in Computer Science (Invited Talk)p. 1
Colorful Stripsp. 2
The Mono-and Bichromatic Empty Rectangle and Square Problems in All Dimensions(Extended Abstract)p. 14
Connectivity Is Not a Limit for Kernelization: Planar Connected Dominating Setp. 26
Randomized Truthful Algorithms for Scheduling Selfish Tasks on Parallel Machinesp. 38
Almost Linear Time Computation of the Chromatic Polynomial of a Graph of Bounded Tree-Widthp. 49
Average Parameterization and Partial Kernelization for Computing Mediansp. 60
Sharp Separation and Applications to Exact and Parameterized Algorithmsp. 72
Finding the Minimum-Distance Schedule for a Boundary Searcher with a Flashlightp. 84
The Language Theory of Bounded Context-Switchingp. 96
Local Search Performance Guarantees for Restricted Related Parallel Machine Schedulingp. 108
Packet Routing on the Gridp. 120
Faithful Representations of Graphs by Islands in the Extended Gridp. 131
The I/O Complexity of Sparse Matrix Dense Matrix Multiplicationp. 143
Sparse Recovery Using Sparse Random Matrices (Invited Talk)p. 157
Optimal Succinctness for Range Minimum Queriesp. 158
Compact Rich-Functional Binary Relation Representationsp. 170
Radix Cross-Sections for Length Morphismsp. 184
Pairs of Complementary Unary Languages with "Balanced" Nondeterministic Automatap. 196
Quotient Complexity of Ideal Languagesp. 208
Complexity of Operations on Confinite Languagesp. 222
Fast Set Intersection and Two-Patterns Matchingp. 234
Counting Reducible, Powerful, and Relatively Irreducible Multivariate Polynomials over Finite Fields (Extended Abstract)p. 243
A Larger Lower Bound on the OBDD Complexity of the Most Significant Bit of Multiplicationp. 255
Modelling the LLL Algorithm by Sandpilesp. 267
Communication-Efficient Construction of the Plane Localized Delaunay Graphp. 282
Time Complexity of Distributed Topological Self-Stabilization: The Case of Graph Linearizationp. 294
Randomised Broadcasting: Memory vs. Randomnessp. 306
Limit Theorems for Random MAX-2-XORSATp. 320
On Quadratic Threshold CSPsp. 332
Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programmingp. 344
Finding the Best CAFE Is NP-Hardp. 356
The Size and Depth of Layered Boolean Circuitsp. 372
Lipschitz Unimodal and Isotonic Regression on Paths and Treesp. 384
Ambiguity and Deficiency in Costas Arrays and APN Permutationsp. 397
Iterated Shared Memory Models(Invited Talk)p. 407
Optimal Polygonal Representation of Planar Graphsp. 417
Minimum-Perimeter Intersecting Polygonsp. 433
Finding the Smallest Gap between Sums of Square Rootsp. 446
Matching Points with Thingsp. 456
Homotopic Rectilinear Routing with Few Links and Thick Edgesp. 468
Tilings Robust to Errorsp. 480
Visiting a Sequence of Points with a Bevel-Tip Needlep. 492
Euclidean Prize-Collecting Steiner Forestp. 503
Prize-Collecting Steiner Networks via Iterative Roundingp. 515
Kernelization through Tidying: A Case Study Based on s-Plex Cluster Vertex Deletionp. 527
Gradual Sub-lattice Reduction and a New Complexity for Factoring Polynomialsp. 539
The Power of Fair Pricing Mechanismsp. 554
Quasi-Proportional Mechanisms: Prior-Free Revenue Maximizationp. 565
Some Observations on Holographic Algorithms (Invited Talk)p. 577
The Interval Constrained 3-Coloring Problemp. 591
Counting Hexagonal Patches and Independent Sets in Circle Graphsp. 603
Approximating Maximum Diameter-Bounded Subgraphsp. 615
Largest Induced Acyclic Tournament in Random Digraphs: A 2-Point Concentrationp. 627
The Complexity of Counting Eulerian Tours in 4-Regular Graphsp. 638
Efficient Edge Domination on Hole-Free Graphs in Polynomial Timep. 650
Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphsp. 662
Rank Selection in Multidimensional Datap. 674
Layered Working-Set Treesp. 686
Lightweight Data Indexing and Compression in External Memoryp. 697
Author Indexp. 711
Table of Contents provided by Ingram. All Rights Reserved.

ISBN: 9783642121999
ISBN-10: 3642121993
Series: Lecture Notes in Computer Science
Audience: General
Format: Paperback
Language: English
Number Of Pages: 712
Published: 9th April 2010
Publisher: Springer-Verlag Berlin and Heidelberg Gmbh & Co. Kg
Country of Publication: DE
Dimensions (cm): 23.37 x 15.49  x 2.54
Weight (kg): 1.02