G. Park, H. -K Hwang, P. Nicodème, W. Szpankowski (auth.), Eduardo Sany Laber, Claudson Bornstein, Loana Tito Nogueira, Luerbio Faria (eds.)3540787720, 9783540787723
The 66 revised full papers presented together with the extended abstract of 1 invited paper were carefully reviewed and selected from 242 submissions. The papers address a veriety of topics in theoretical computer science with a certain focus on algorithms, automata theory and formal languages, coding theory and data compression, algorithmic graph theory and combinatorics, complexity theory, computational algebra, computational biology, computational geometry, computational number theory, cryptography, theoretical aspects of databases and information retrieval, data structures, networks, logic in computer science, machine learning, mathematical programming, parallel and distributed computing, pattern matching, quantum computing and random structures.
Table of contents :
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 –
Reviews
There are no reviews yet.