Algorithms and Data Structures

Contenu

Session 1.- Towards a Theory of Algorithms.- Session 2A.- k-Restricted Rotation with an Application to Search Tree Rebalancing.- Heap Building Bounds.- Session 2B.- The Multi-radius Cover Problem.- Parameterized Complexity of Generalized Vertex Cover Problems.- The Complexity of Implicit and Space Efficient Priority Queues.- Analysis of a Class of Tries with Adaptive Multi-digit Branching.- Balanced Aspect Ratio Trees Revisited.- Session 3B.- Improved Combinatorial Group Testing for Real-World Problem Sizes.- Parameterized Counting Algorithms for General Graph Covering Problems.- Approximating the Online Set Multicover Problems via Randomized Winnowing.- Session 4A.- Max-stretch Reduction for Tree Spanners.- Succinct Representation of Triangulations with a Boundary.- Line-Segment Intersection Made In-Place.- Session 4B.- Improved Fixed-Parameter Algorithms for Two Feedback Set Problems.- Communication-Aware Processor Allocation for Supercomputers.- Dynamic Hotlinks.- Session 6A.- The Minimum-Area Spanning Tree Problem.- Hinged Dissection of Polypolyhedra.- Session 6B.- Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms.- Linear Time Algorithms for Generalized Edge Dominating Set Problems.- Session 7A.- On Geometric Dilation and Halving Chords.- Orthogonal Subdivisions with Low Stabbing Numbers.- Kinetic and Dynamic Data Structures for Convex Hulls and Upper Envelopes.- Session 7B.- Approximation Algorithms for Forests Augmentation Ensuring Two Disjoint Paths of Bounded Length.- A Dynamic Implicit Adjacency Labelling Scheme for Line Graphs.- The On-line Asymmetric Traveling Salesman Problem.- Session 8A.- All-Pairs Shortest Paths with Real Weights in O(n 3/log n) Time.- k-Link Shortest Paths in Weighted Subdivisions.- Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices.- Session 8B.- Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems.- On the Vehicle Routing Problem.- Session 9A.- The Structure of Optimal Prefix-Free Codes in Restricted Languages: The Uniform Probability Case.- Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms.- Derandomization of Dimensionality Reduction and SDP Based Algorithms.- Session 9B.- Subquadratic Algorithms for 3SUM.- Near-Optimal Pricing in Near-Linear Time.- Improved Approximation Bounds for Planar Point Pattern Matching.