Algorithms and Data Structures 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings / [electronic resource] :
edited by Frank Dehne, Alejandro López-Ortiz, Jörg-Rüdiger Sack.
- 1st ed. 2005.
- XIV, 446 p. online resource.
- Theoretical Computer Science and General Issues, 3608 2512-2029 ; .
- Theoretical Computer Science and General Issues, 3608 .
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-SavingScheduling 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.
9783540317111
10.1007/11534273 doi
Algorithms.
Artificial intelligence--Data processing.
Computer science--Mathematics.
Discrete mathematics.
Computer graphics.
Numerical analysis.
Algorithms.
Data Science.
Discrete Mathematics in Computer Science.
Computer Graphics.
Numerical Analysis.
QA76.9.A43
518.1
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-SavingScheduling 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.
9783540317111
10.1007/11534273 doi
Algorithms.
Artificial intelligence--Data processing.
Computer science--Mathematics.
Discrete mathematics.
Computer graphics.
Numerical analysis.
Algorithms.
Data Science.
Discrete Mathematics in Computer Science.
Computer Graphics.
Numerical Analysis.
QA76.9.A43
518.1