Algorithms and Computation

Puzzles, Art, and Magic with Algorithms.- The ABCs of AVDs: Geometric Retrieval Made Simple.- Pareto Optimality in House Allocation Problems.- Property-Preserving Data Reconstruction.- On the Monotone Circuit Complexity of Quadratic Boolean Functions.- Generalized Function Matching.- Approximate Distance Oracles for Graphs with Dense Clusters.- Multicriteria Global Minimum Cuts.- Polyline Fitting of Planar Points Under Min-sum Criteria.- A Generalization of Magic Squares with Applications to Digital Halftoning.- Voronoi Diagrams with a Transportation Network on the Euclidean Plane.- Structural Alignment of Two RNA Sequences with Lagrangian Relaxation.- Poly-APX- and PTAS-Completeness in Standard and Differential Approximation.- Efficient Algorithms for k Maximum Sums.- Equipartitions of Measures by 2-Fans.- Augmenting the Edge-Connectivity of a Spider Tree.- On Nash Equilibria for Multicast Transmissions in Ad-Hoc Wireless Networks.- Structural Similarity in Graphs.- Flexibility of Steiner Trees in Uniform Orientation Metrics.- Random Access to Advice Strings and Collapsing Results.- Bounding the Payment of Approximate Truthful Mechanisms.- The Polymatroid Steiner Problems.- Geometric Optimization Problems Over Sliding Windows.- On-Line Windows Scheduling of Temporary Items.- Generalized Geometric Approaches for Leaf Sequencing Problems in Radiation Therapy.- An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem.- On the Range Maximum-Sum Segment Query Problem.- An Efficient Algorithm for Finding Maximum Cycle Packings in Reducible Flow Graphs.- Efficient Job Scheduling Algorithms with Multi-type Contentions.- Superimposing Voronoi Complexes for Shape Deformation.- On Partial Lifting and the Elliptic Curve Discrete Logarithm Problem.- Guarding Art Galleries by Guarding Witnesses.- On p-Norm Based Locality Measures of Space-Filling Curves.- Composability of Infinite-State Activity Automata.- Error Compensation in Leaf Root Problems.- On Compact and Efficient Routing in Certain Graph Classes.- Randomized Insertion and Deletion in Point Quad Trees.- Diagnosis in the Presence of Intermittent Faults.- Three-Round Adaptive Diagnosis in Binary n-Cubes.- Fast Algorithms for Comparison of Similar Unordered Trees.- GCD of Random Linear Forms.- On the Hardness and Easiness of Random 4-SAT Formulas.- Minimum Common String Partition Problem: Hardness and Approximations.- On the Complexity of Network Synchronization.- Counting Spanning Trees and Other Structures in Non-constant-jump Circulant Graphs.- Adaptive Spatial Partitioning for Multidimensional Data Streams.- Paired Pointset Traversal.- Approximated Two Choices in Randomized Load Balancing.- Space-Efficient and Fast Algorithms for Multidimensional Dominance Reporting and Counting.- Local Gapped Subforest Alignment and Its Application in Finding RNA Structural Motifs.- The Maximum Agreement of Two Nested Phylogenetic Networks.- Sequences of Radius k: How to Fetch Many Huge Objects into Small Memory for Pairwise Computations.- New Bounds on Map Labeling with Circular Labels.- Optimal Buffer Management via Resource Augmentation.- Oriented Paths in Mixed Graphs.- Polynomial Deterministic Rendezvous in Arbitrary Graphs.- Distributions of Points and Large Quadrangles.- Cutting Out Polygons with Lines and Rays.- Advantages of Backward Searching — Efficient Secondary Memory and Distributed Implementation of Compressed Suffix Arrays.- Inner Rectangular Drawings of Plane Graphs.- Approximating the Minmax Subtree Cover Problem in a Cactus.- Boundary-Optimal Triangulation Flooding.- Exact Computation of Polynomial Zeros Expressible by Square Roots.- Many-to-Many Disjoint Path Covers in a Graph with Faulty Elements.- An O(nlog n)-Time Algorithm for the Maximum Constrained Agreement Subtree Problem for Binary Trees.- Planning the Transportation of Multiple Commodities in Bidirectional Pipeline Networks.- Efficient Algorithms for the Hotlink Assignment Problem: The Worst Case Search.- Dynamic Tree Cross Products.- Spanners, Weak Spanners, and Power Spanners for Wireless Networks.- Techniques for Indexing and Querying Temporal Observations for a Collection of Objects.- Approximation Algorithms for the Consecutive Ones Submatrix Problem on Sparse Matrices.- The Two-Guard Problem Revisited and Its Generalization.- Canonical Data Structure for Interval Probe Graphs.- Efficient Algorithms for the Longest Path Problem.- Randomized Algorithms for Motif Detection.- Weighted Coloring on Planar, Bipartite and Split Graphs: Complexity and Improved Approximation.- Sweeping Graphs with Large Clique Number.- A Slightly Improved Sub-cubic Algorithm for the All Pairs Shortest Paths Problem with Real Edge Lengths.