LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, B˙zios, Brazil, April 7-11, 2008, Proceedings

Front Cover
Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria
Springer Science & Business Media, Mar 17, 2008 - Computers - 794 pages
The Latin American Theoretical INformatics Symposium (LATIN) is becoming a traditional and high-quality conference on the Theory of Computing. Previous conferenceshavebeenorganizedtwiceinBrazil: S aoPaulo(1992)andCampinas (1998); twice in Chile: Valpara ?so (1995) and Valdivia (2006); once in Uruguay: Punta del Este (2000); once in Mexico: Cancun (2002); and once in Argentina: Buenos Aires (2004). This volume contains the proceedings of the 8th Latin American Theore- cal INformatics Symposium (LATIN 2008), which was held in Buzio s, Rio de Janeiro, Brazil, April 7 11, 2008. Atotalof242paperswerereviewedbytheprogramcommittee.Amongthem, 66 were selected for presentation at the conference. The selection was based on the papers originality, quality and relevance to Theoretical Computer Science. This volume also contains the extended abstract associated with the invited talk of Wojciech Szpankowski. We also had 4 invited talks by Cl audio Leonardo Lucchesi, Eva Tardos, Moni Naor and Robert Tarjan. We wouldlike to thank allmembers ofthe PCfortheir thoroughwork, which resultedinagoodselectionofpapers;themembersoftheSteeringCommitteefor their insightfuladviceandforsharingtheir experiencewithus;andthe members of our community who served as referees. Inaddition, wethankalloursponsors, Microsoft, UOL, IFIP, HP, Yahoo!, FAPERJ, CNPq and CAPES, and Springer for their continuous support."
 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Profile of Tries
1
Random 2XORSAT at the Satisfiability Threshold
12
On Dissemination Thresholds in Regular and Irregular Graph Classes
24
How to Complete a Doubling Metric
36
Sorting and Selection with Random Costs
48
Guided Search and a Faster Deterministic Algorithm for 3SAT
60
Comparing and Aggregating Partially Resolved Trees
72
Computing the Growth of the Number of OverlapFree Words with Spectra of Matrices
84
Approximating Steiner Networks with Node Weights
411
Approximating MinimumPower Degree and Connectivity Problems
423
Energy Efficient Monitoring in Sensor Networks
436
Approximation Algorithms for kHurdle Problems
449
Approximating Crossing Minimization in Radial Layouts
461
New Upper Bound on Vertex Folkman Numbers
473
Ptolemaic Graphs and Interval Graphs Are Leaf Powers
479
A Representation Theorem for UnionDifference Families and Application Extended Abstract
492

Hierarchies and the Emptiness Problem
94
MyhillNerode Theorem for Recognizable Tree Series Revisited
106
The View Selection Problem for Regular Path Queries
121
Optimal Higher Order Delaunay Triangulations of Polygons
133
Coloring Geometric Range Spaces
146
Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes
158
Spanners of Complete kPartite Geometric Graphs
170
Minimum Cost Homomorphisms to Reflexive Digraphs
182
On the Complexity of Reconstructing Hfree Graphs from Their Star Systems
194
Optimization and Recognition for K₅minor Free Graphs in Linear Time
206
Bandwidth of Bipartite Permutation Graphs in Polynomial Time
216
On the Exponential Boost of One Extra Server
228
Average Rate Speed Scaling
240
An Optimal Randomized Algorithm for Two Buffers
252
Maximizing the Minimum Load for Selfish Agents
264
Small Degree and Small Height Perturbations
276
Pseudorandom Graphs from Elliptic Curves
284
SpeedingUp Lattice Reduction with Random Projections Extended Abstract
293
Sparse Approximate Solutions to Semidefinite Programs
306
On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints
317
A Polyhedral Investigation of the LCS Problem and a RepetitionFree Variant
329
Competitive Cost Sharing with Economies of Scale
339
Emergency Connectivity in AdHoc Networks with Selfish Nodes
350
FullyCompressed Suffix Trees
362
Improved Dynamic RankSelect EntropyBound Structures
374
An Improved Algorithm Finding Nearest Neighbor Using Kdtrees
387
List Update with Locality of Reference
399
Algorithms to Locate Errors Using Covering Arrays
504
On Injective Colourings of Chordal Graphs
520
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms
531
On 2Subcolourings of Chordal Graphs
544
Collective Additive Tree Spanners of Homogeneously Orderable Graphs Extended Abstract
555
Finding Them Is Not That Easy
568
Stateless Near Optimal Flow Control with Polylogarithmic Convergence
580
The LeastUnpopularityFactor and LeastUnpopularityMargin Criteria for Matching Problems with OneSided Preferences
593
Randomized RendezVous with Limited Memory
605
Origami Embedding of PiecewiseLinear TwoManifolds
617
Simplifying 3D Polygonal Chains Under the Discrete FrÚchet Distance
630
in the Plane
642
Paths with no Small Angles
654
Simpler ConstantSeed Condensers
664
Parallel Repetition of the Odd Cycle Game
676
IOEfficient Point Location in a Set of Rectangles
687
Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream
699
FixedParameter Algorithms for Cluster Vertex Deletion
711
Paths and Trails in EdgeColored Graphs
723
Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs
736
Domination in Geometric Intersection Graphs
747
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil2 Groups
759
Quantum Property Testing of Group Solvability
772
Solving NPComplete Problems with Quantum Search
784
Author Index
793
Copyright

Other editions - View all

Common terms and phrases