Algorithms and Computation: 26th International Symposium, ISAAC 2015, Nagoya, Japan, December 9-11, 2015, Proceedings (Lecture Notes in Computer Science Book 9472)

This book constitutes the refereed proceedings of the 26th International Symposium on Algorithms and Computation, ISAAC 2015, held in Nagoya, Japan, in December 2015. The 65 revised full papers presented together with 3 invited talks were carefully reviewed and selected from 180 submissions for inclusion in the book. The focus of the volume is on the following topics: computational geometry; data structures; combinatorial optimization and approximation algorithms; randomized algorithms; graph algorithms and FPT; computational complexity; graph drawing and planar graphs; online and streaming algorithms; and string and DNA algorithms. Front Matter....Pages I-XXII Front Matter....Pages 1-1 An Optimal Algorithm for Tiling the Plane with a Translated Polyomino....Pages 3-13 Adaptive Point Location in Planar Convex Subdivisions....Pages 14-22 Competitive Local Routing with Constraints....Pages 23-34 Navigating Weighted Regions with Scattered Skinny Tetrahedra....Pages 35-45 Front Matter....Pages 47-47 On the Succinct Representation of Unlabeled Permutations....Pages 49-59 How to Select the Top k Elements from Evolving Data?....Pages 60-70 Optimal Search Trees with 2-Way Comparisons....Pages 71-82 Multidimensional Range Selection....Pages 83-92 Front Matter....Pages 93-93 On the Minimum Cost Range Assignment Problem....Pages 95-105 On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems....Pages 106-115 General Caching Is Hard: Even with Small Pages....Pages 116-126 Front Matter....Pages 127-127 The Secretary Problem with a Choice Function....Pages 129-139 The Benefit of Recombination in Noisy Evolutionary Search....Pages 140-150 Algorithmic Learning for Steganography: Proper Learning of k-term DNF Formulas from Positive Samples....Pages 151-162 Front Matter....Pages 163-163 Obtaining a Triangular Matrix by Independent Row-Column Permutations....Pages 165-175 Many-to-one Matchings with Lower Quotas: Algorithms and Complexity....Pages 176-187 Minimizing the Maximum Moving Cost of Interval Coverage....Pages 188-198 Front Matter....Pages 199-199 Heuristic Time Hierarchies via Hierarchies for Sampling Distributions....Pages 201-211 Unbounded Discrepancy of Deterministic Random Walks on Grids....Pages 212-222 Trading off Worst and Expected Cost in Decision Tree Problems....Pages 223-234 Front Matter....Pages 235-235 Sliding Token on Bipartite Permutation Graphs....Pages 237-247 Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width....Pages 248-258 Minimum Degree Up to Local Complementation: Bounds, Parameterized Complexity, and Exact Algorithms....Pages 259-270 Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs....Pages 271-282 Front Matter....Pages 283-283 Geometric Matching Algorithms for Two Realistic Terrains....Pages 285-295 Size-Dependent Tile Self-Assembly: Constant-Height Rectangles and Stability....Pages 296-306 The 2-Center Problem in a Simple Polygon....Pages 307-317 Choice Is Hard....Pages 318-328 Front Matter....Pages 329-329 Fully Dynamic Betweenness Centrality....Pages 331-342 When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots....Pages 343-354 Cops and Robbers on String Graphs....Pages 355-366 Min-Power Covering Problems....Pages 367-377 Front Matter....Pages 379-379 Minimizing the Diameter of a Spanning Tree for Imprecise Points....Pages 381-392 Model-Based Classification of Trajectories....Pages 393-403 Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures....Pages 404-414 Unfolding Orthogonal Polyhedra with Linear Refinement....Pages 415-425 Front Matter....Pages 427-427 Colored Non-crossing Euclidean Steiner Forest....Pages 429-441 On a Generalization of Nemhauser and Trotter’s Local Optimization Theorem....Pages 442-452 Approximation Algorithms in the Successive Hitting Set Model....Pages 453-464 Front Matter....Pages 465-465 Generating Random Hyperbolic Graphs in Subquadratic Time....Pages 467-478 Front Matter....Pages 465-465 Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing....Pages 479-490 Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty....Pages 491-501 Front Matter....Pages 503-503 An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings....Pages 505-516 Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds....Pages 517-528 Computing the Gromov-Hausdorff Distance for Metric Trees....Pages 529-540 The VC-Dimension of Visibility on the Boundary of a Simple Polygon....Pages 541-551 Front Matter....Pages 553-553 Quantum Bit Commitment with Application in Quantum Zero-Knowledge Proof (Extended Abstract)....Pages 555-565 Effectiveness of Structural Restrictions for Hybrid CSPs....Pages 566-577 Polynomial-Time Isomorphism Test of Groups that are Tame Extensions....Pages 578-589 Quantum Algorithm for Triangle Finding in Sparse Graphs....Pages 590-600 Front Matter....Pages 601-601 On Hardness of the Joint Crossing Number....Pages 603-613 Partitioning Graph Drawings and Triangulated Simple Polygons into Greedily Routable Regions....Pages 614-624 Front Matter....Pages 625-636 A New Approximate Min-Max Theorem with Applications in Cryptography....Pages 637-649 Give Me Another One!....Pages 651-651 On the Complexity of Computing Prime Tables....Pages 653-663 Game Values and Computational Complexity: An Analysis via Black-White Combinatorial Games....Pages 664-676 Front Matter....Pages 677-688 Run Generation Revisited: What Goes Up May or May Not Come Down....Pages 689-699 Streaming Verification in Data Analysis....Pages 701-701 Front Matter....Pages 703-714 All-Around Near-Optimal Solutions for the Online Bin Packing Problem....Pages 715-726 Serving Online Requests with Mobile Servers....Pages 701-701 Front Matter....Pages 727-739 An In-place Framework for Exact and Approximate Shortest Unique Substring Queries....Pages 740-751 Inferring Strings from Full Abelian Periods....Pages 753-753 Toehold DNA Languages are Regular (Extended Abstract)....Pages 755-767 Back Matter....Pages 768-779 ....Pages 780-790