## LATIN 2008: Theoretical Informatics: 8th Latin American Symposium, Búzios, Brazil, April 7-11, 2008, ProceedingsEduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria 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

Proﬁle of Tries | 1 |

Random 2XORSAT at the Satisﬁability 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 Efﬁcient 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 Reﬂexive 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 Selﬁsh 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 Semideﬁnite 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 Selﬁsh 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 |

793 | |

### Other editions - View all

### Common terms and phrases

apply approximation algorithm Berlin Heidelberg 2008 bipartite bipartite graph chordal graphs color competitive ratio components connected consider constant construct contains corresponding cost cover cycle data structure decomposition deﬁned Deﬁnition denote deterministic diﬀerent digraph disk distance dominating set E.S. Laber Edge-Colored eﬃcient elements exists factor ﬁnd ﬁnding ﬁnite ﬁrst ﬁxed ﬂow function given graph G Hence induced induced subgraph inequality input instance integer intersection intersection graphs interval graphs Kd-tree leaf least Lemma linear LNCS matrix maximal metric minimal minimum node NP-complete NP-hard O(log obtain online algorithm optimal pair partition path permutation graphs polygon polynomial problem Proof Properly Edge-Colored prove quantum query random ratio rectangles result satisﬁes sequence solution solvable solvable group space spanning tree Springer stable matching subgraph subset suﬃx Theorem tree spanners triangle unit disk graphs variables vector vertex vertices viewset weight