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

Front Matter....Pages -
Profile of Tries....Pages 1-11
Random 2-XORSAT at the Satisfiability Threshold....Pages 12-23
On Dissemination Thresholds in Regular and Irregular Graph Classes....Pages 24-35
How to Complete a Doubling Metric....Pages 36-47
Sorting and Selection with Random Costs....Pages 48-59
Guided Search and a Faster Deterministic Algorithm for 3-SAT....Pages 60-71
Comparing and Aggregating Partially Resolved Trees....Pages 72-83
Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices....Pages 84-93
On Stateless Multihead Automata: Hierarchies and the Emptiness Problem....Pages 94-105
Myhill-Nerode Theorem for Recognizable Tree Series Revisited....Pages 106-120
The View Selection Problem for Regular Path Queries....Pages 121-132
Optimal Higher Order Delaunay Triangulations of Polygons....Pages 133-145
Coloring Geometric Range Spaces....Pages 146-157
Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes....Pages 158-169
Spanners of Complete k -Partite Geometric Graphs....Pages 170-181
Minimum Cost Homomorphisms to Reflexive Digraphs....Pages 182-193
On the Complexity of Reconstructing H -free Graphs from Their Star Systems....Pages 194-205
Optimization and Recognition for K 5 -minor Free Graphs in Linear Time....Pages 206-215
Bandwidth of Bipartite Permutation Graphs in Polynomial Time....Pages 216-227
The Online Transportation Problem: On the Exponential Boost of One Extra Server....Pages 228-239
Average Rate Speed Scaling....Pages 240-251
Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers....Pages 252-263
Maximizing the Minimum Load for Selfish Agents....Pages 264-275
Approximate Polynomial gcd: Small Degree and Small Height Perturbations....Pages 276-283
Pseudorandom Graphs from Elliptic Curves....Pages 284-292
Speeding-Up Lattice Reduction with Random Projections (Extended Abstract)....Pages 293-305
Sparse Approximate Solutions to Semidefinite Programs....Pages 306-316
On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints....Pages 317-328
A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant....Pages 329-338
Competitive Cost Sharing with Economies of Scale....Pages 339-349
Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes....Pages 350-361
Fully-Compressed Suffix Trees....Pages 362-373
Improved Dynamic Rank-Select Entropy-Bound Structures....Pages 374-386
An Improved Algorithm Finding Nearest Neighbor Using Kd-trees....Pages 387-398
List Update with Locality of Reference....Pages 399-410
Approximating Steiner Networks with Node Weights....Pages 411-422
Approximating Minimum-Power Degree and Connectivity Problems....Pages 423-435
Energy Efficient Monitoring in Sensor Networks....Pages 436-448
Approximation Algorithms for k -Hurdle Problems....Pages 449-460
Approximating Crossing Minimization in Radial Layouts....Pages 461-472
New Upper Bound on Vertex Folkman Numbers....Pages 473-478
Ptolemaic Graphs and Interval Graphs Are Leaf Powers....Pages 479-491
A Representation Theorem for Union-Difference Families and Application....Pages 492-503
Algorithms to Locate Errors Using Covering Arrays....Pages 504-519
On Injective Colourings of Chordal Graphs....Pages 520-530
Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms....Pages 531-543
On 2-Subcolourings of Chordal Graphs....Pages 544-554
Collective Additive Tree Spanners of Homogeneously Orderable Graphs....Pages 555-567
The Generalized Median Stable Matchings: Finding Them Is Not That Easy....Pages 568-579
Stateless Near Optimal Flow Control with Poly-logarithmic Convergence....Pages 580-592
The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences....Pages 593-604
Randomized Rendez-Vous with Limited Memory....Pages 605-616
Origami Embedding of Piecewise-Linear Two-Manifolds....Pages 617-629
Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance....Pages 630-641
Weighted Rectilinear Approximation of Points in the Plane....Pages 642-653
Paths with no Small Angles....Pages 654-663
Simpler Constant-Seed Condensers....Pages 664-675
Parallel Repetition of the Odd Cycle Game....Pages 676-686
I/O-Efficient Point Location in a Set of Rectangles....Pages 687-698
Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream....Pages 699-710
Fixed-Parameter Algorithms for Cluster Vertex Deletion....Pages 711-722
Paths and Trails in Edge-Colored Graphs....Pages 723-735
Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs....Pages 736-746
Domination in Geometric Intersection Graphs....Pages 747-758
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups....Pages 759-771
Quantum Property Testing of Group Solvability....Pages 772-783
Solving NP-Complete Problems with Quantum Search....Pages 784-792
Back Matter....Pages -