Latin 2008 theoretical informatics : 8th Latin American symposium, Búzios, Brazil, April 7-11, 2008 : proceedings / Eduardo Sany Laber ... [et al.] (eds.)

Author(s): Latin American Symposium on Theoretical Informatics (8th : 2008 : Armação dos Búzios, Brazil)
Online: Connect to OhioLINK EBC
Location:
Retrieving Holdings Information
Subjects: Computer science--Latin America--Congresses
Electronic books
Formats: Electronic Resource, Remote
Material Type: Books
Language: English
Audience: Unspecified
Published: Berlin ; New York : Springer, 2008
Series: Lecture notes in computer science 4957
LNCS sublibrary. SL 1. Theoretical computer science and general issues
Table of Contents: Profile of Tries 1
Random 2-XORSAT at the Satisfiability Threshold 12
On Disseminatiou 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 3-SAT 60
Comparing and Aggregating Partially Resolved Trees 72
Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices 84
On Stateless Multihead Automata: Hierarchies and the Emptiness Problem 94
Myhill-Nerode 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 k-Partite Geometric Graphs 170
Minimum Cost Homomorphisms to Reflexive Digraphs 182
On the Complexity of Reconstructing H-free Graphs from Their Star Systems 194
Optimization and Recognition for K[subscript 5]-minor Free Graphs in Linear Tillie 206
Bandwidth of Bipartite Permutation Graphs in Polynomial Time 210
The Online Transportation Problem: On the Exponential Boost of One Extra Server 228
Average Rate Speed Scaling 240
Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers 252
Maximizing the Minimum Load for Selfish Agents 264
Approximate Polynomial gcd: Small Degree and Small Height Perturbations 270
Pseudorandom Graphs from Elliptic Curves 284
Speeding-Up 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 Repetition-Free Variant 329
Competitive Cost Sharing with Economics of Scale 339
Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes 350
Fully-Compressed Suffix Trees 362
Improved Dynamic Rank-Select Entropy-Bound Structures 374
An Improved Algorithm Finding Nearest Neighbor Using Kd-trees 387
List Updatc with Locality of Reference 399
Approximating Steiner Networks with Node Weights 411
Approximating Minimum-Power Degree and Connectivity Problems 423
Energy Efficient Monitoring in Sensor Networks 436
Approximation Algorithms for k-Hmdle 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 Union-Difference Families and Application (Extended Abstract) 492
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 2-Subcolourings of Chordal Graphs 544
Collective Additive Tree Spanners of Homogeneously Orderable Graphs (Extended Abstract) 555
The Generalized Median Stable Matchings: Finding Them Is Not That Easy 568
Stateless Near Optimal Flow Control with Poly-logarithmic Convergence 580
The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences 593
Randomized Rendez-Vous with Limited Memory 605
Origami Embedding of Piecewise-Linear Two-Manifolds 617
Simplifying 3D Polygonal Chains Under the Discrete Frechet Distance 630
Weighted Rectilinear Approximation of Points in the Plane 642
Paths with no Small Angles 654
Simpler Constant-Seed Condensers 664
Parallel Repetition of the Odd Cycle Game 676
I/O-Efficient Point Location in a Set of Rectangles 687
Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream 699
Fixed-Parameter Algorithms for Cluster Vertex Deletion 711
Paths and Trails in Edge-Colored Graphs 723
Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs 736
Domination in Geometric Intersection Graphs 747
An Etficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups 759
Quantum Property Testing of Croup Solvability 772
Solving NP-Complete Problems with Quantum Search 784
Author Index 793
Alternate Titles: In: SpringerLink (OCoLC)43927870
In: OhioLINK electronic book center (Online) (OCoLC)180989150
Additional Authors: Laber, Eduardo Sany
SpringerLink (Online service)
Notes: ISBN: 9783540787723
ISBN: 3540787720
ISBN: 9783540787730 (ebook)
ISBN: 3540787739 (ebook)
Available to OhioLINK libraries
Includes bibliographical references and index
Reproduction notes: Electronic reproduction. Berlin : Springer, 2008. System requirements: Adobe Acrobat Reader and Internet browser; text in HTML and PDF. Mode of access: World Wide Web. Title from title screen; description based on content as of July 26, 2008. Access restricted to subscribing institution. Also available in print
Physical Description: xvii, 794 p. : ill. ; 24 cm
OCLC Number: 233974025
ISBN/ISSN: 9783540787723
3540787720
9783540787730
3540787739

Miami University Libraries | 151 South Campus Avenue | Oxford, Ohio 45056 | 513.529.4141 | Miami University | myMiami | Staff Area