LATIN 2008: Theoretical Informatics

This proceedings volume examines a range of topics in theoretical computer science, including automata theory, data compression, logic, machine learning, mathematical programming, parallel and distributed computing, quantum computing and random structures.

Inhalt

Profile of Tries.- Random 2-XORSAT at the Satisfiability Threshold.- On Dissemination Thresholds in Regular and Irregular Graph Classes.- How to Complete a Doubling Metric.- Sorting and Selection with Random Costs.- Guided Search and a Faster Deterministic Algorithm for 3-SAT.- Comparing and Aggregating Partially Resolved Trees.- Computing the Growth of the Number of Overlap-Free Words with Spectra of Matrices.- On Stateless Multihead Automata: Hierarchies and the Emptiness Problem.- Myhill-Nerode Theorem for Recognizable Tree Series Revisited.- The View Selection Problem for Regular Path Queries.- Optimal Higher Order Delaunay Triangulations of Polygons.- Coloring Geometric Range Spaces.- Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes.- Spanners of Complete k-Partite Geometric Graphs.- Minimum Cost Homomorphisms to Reflexive Digraphs.- On the Complexity of Reconstructing H-free Graphs from Their Star Systems.- Optimization and Recognition for K 5-minor Free Graphs in Linear Time.- Bandwidth of Bipartite Permutation Graphs in Polynomial Time.- The Online Transportation Problem: On the Exponential Boost of One Extra Server.- Average Rate Speed Scaling.- Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers.- Maximizing the Minimum Load for Selfish Agents.- Approximate Polynomial gcd: Small Degree and Small Height Perturbations.- Pseudorandom Graphs from Elliptic Curves.- Speeding-Up Lattice Reduction with Random Projections (Extended Abstract).- Sparse Approximate Solutions to Semidefinite Programs.- On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints.- A Polyhedral Investigation of the LCS Problem and a Repetition-Free Variant.- Competitive Cost Sharing with Economies of Scale.- Emergency Connectivity in Ad-Hoc Networks with Selfish Nodes.- Fully-Compressed Suffix Trees.- Improved Dynamic Rank-Select Entropy-Bound Structures.- An Improved Algorithm Finding Nearest Neighbor Using Kd-trees.- List Update with Locality of Reference.- Approximating Steiner Networks with Node Weights.- Approximating Minimum-Power Degree and Connectivity Problems.- Energy Efficient Monitoring in Sensor Networks.- Approximation Algorithms for k-Hurdle Problems.- Approximating Crossing Minimization in Radial Layouts.- New Upper Bound on Vertex Folkman Numbers.- Ptolemaic Graphs and Interval Graphs Are Leaf Powers.- A Representation Theorem for Union-Difference Families and Application.- Algorithms to Locate Errors Using Covering Arrays.- On Injective Colourings of Chordal Graphs.- Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms.- On 2-Subcolourings of Chordal Graphs.- Collective Additive Tree Spanners of Homogeneously Orderable Graphs.- The Generalized Median Stable Matchings: Finding Them Is Not That Easy.- Stateless Near Optimal Flow Control with Poly-logarithmic Convergence.- The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences.- Randomized Rendez-Vous with Limited Memory.- Origami Embedding of Piecewise-Linear Two-Manifolds.- Simplifying 3D Polygonal Chains Under the Discrete Fréchet Distance.- Weighted Rectilinear Approximation of Points in the Plane.- Paths with no Small Angles.- Simpler Constant-Seed Condensers.- Parallel Repetition of the Odd Cycle Game.- I/O-Efficient Point Location in a Set of Rectangles.- Finding Heavy Hitters over the Sliding Window of a Weighted Data Stream.- Fixed-Parameter Algorithms for Cluster Vertex Deletion.- Paths and Trails in Edge-Colored Graphs.- Efficient Approximation Algorithms for Shortest Cycles in Undirected Graphs.- Domination in Geometric Intersection Graphs.- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Nil-2 Groups.- Quantum Property Testing of Group Solvability.- Solving NP-Complete Problems with Quantum Search.