9. WADS 2005: Waterloo, Canada

Frank K. H. A. Dehne, Alejandro López-Ortiz, Jörg-Rüdiger Sack (Eds.): Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings. Lecture Notes in Computer Science 3608 Springer 2005, ISBN 3-540-28101-0

Session 1

Alejandro Almeida Ruiz, Fabrizio Luccio, Antonio Mesa Enriques, Linda Pagli:
k-Restricted Rotation with an Application to Search Tree Rebalancing. 2-13
Zhentao Li, Bruce A. Reed:
Heap Building Bounds. 14-23

Refael Hassin, Danny Segev:
The Multi-radius Cover Problem. 24-35
Jiong Guo, Rolf Niedermeier, Sebastian Wernicke:
Parameterized Complexity of Generalized Vertex Cover Problems. 36-48
Christian Worm Mortensen, Seth Pettie:
The Complexity of Implicit and Space Efficient Priority Queues. 49-60
Yuriy A. Reznik:
Analysis of a Class of Tries with Adaptive Multi-digit Branching. 61-72
Amitabh Chaudhary, Michael T. Goodrich:
Balanced Aspect Ratio Trees Revisited. 73-85

David Eppstein, Michael T. Goodrich, Daniel S. Hirschberg:
Improved Combinatorial Group Testing for Real-World Problem Sizes. 86-98
Naomi Nishimura, Prabhakar Ragde, Dimitrios M. Thilikos:
Parameterized Counting Algorithms for General Graph Covering Problems. 99-109
Piotr Berman, Bhaskar DasGupta:
Approximating the Online Set Multicover Problems via Randomized Winnowing. 110-121

Kazuo Iwama, Andrzej Lingas, Masaki Okita:
Max-stretch Reduction for Tree Spanners. 122-133
Luca Castelli Aleardi, Olivier Devillers, Gilles Schaeffer:
Succinct Representation of Triangulations with a Boundary. 134-145
Jan Vahrenhold:
Line-Segment Intersection Made In-Place. 146-157

Jiong Guo, Jens Gramm, Falk Hüffner, Rolf Niedermeier, Sebastian Wernicke:
Improved Fixed-Parameter Algorithms for Two Feedback Set Problems. 158-168
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips:
Communication-Aware Processor Allocation for Supercomputers. 169-181
Karim Douïeb, Stefan Langerman:
Dynamic Hotlinks. 182-194

Paz Carmi, Matthew J. Katz, Joseph S. B. Mitchell:
The Minimum-Area Spanning Tree Problem. 195-204
Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine:
Hinged Dissection of Polypolyhedra. 205-217

Shlomo Moran, Sagi Snir:
Convex Recolorings of Strings and Trees: Definitions, Hardness Results and Algorithms. 218-232
André Berger, Ojas Parekh:
Linear Time Algorithms for Generalized Edge Dominating Set Problems. 233-243

Adrian Dumitrescu, Annette Ebbers-Baumann, Ansgar Grüne, Rolf Klein, Günter Rote:
On Geometric Dilation and Halving Chords. 244-255
Csaba D. Tóth:
Orthogonal Subdivisions with Low Stabbing Numbers. 256-268
Giora Alexandron, Haim Kaplan, Micha Sharir:
Kinetic and Dynamic Data Structures for Convex Hulls and Upper Envelopes. 269-281

Victor Chepoi, Bertrand Estellon, Yann Vaxès:
Approximation Algorithms for Forests Augmentation Ensuring Two Disjoint Paths of Bounded Length. 282-293
David Morgan:
A Dynamic Implicit Adjacency Labelling Scheme for Line Graphs. 294-305
Giorgio Ausiello, Vincenzo Bonifaci, Luigi Laura:
The On-line Asymmetric Traveling Salesman Problem. 306-317

Timothy M. Chan:
All-Pairs Shortest Paths with Real Weights in O(n³/log n) Time. 318-324
Ovidiu Daescu, Joseph S. B. Mitchell, Simeon C. Ntafos, James D. Palmer, Chee-Keng Yap:
k-Link Shortest Paths in Weighted Subdivisions. 325-337
Jian-Jia Chen, Tei-Wei Kuo, Hsueh-I Lu:
Power-Saving Scheduling for Weakly Dynamic Voltage Scaling Devices. 338-349

Markus Bläser, L. Shankar Ram, Maxim Sviridenko:
Improved Approximation Algorithms for Metric Maximum ATSP and Maximum 3-Cycle Cover Problems. 350-359
Piotr Berman, Surajit K. Das:
On the Vehicle Routing Problem. 360-371

Mordecai J. Golin, Zhenming Liu:
The Structure of Optimal Prefix-Free Codes in Restricted Languages: The Uniform Probability Case. 372-384
Gerth Stølting Brodal, Gabriel Moruz:
Tradeoffs Between Branch Mispredictions and Comparisons for Sorting Algorithms. 385-395
Ankur Bhargava, S. Rao Kosaraju:
Derandomization of Dimensionality Reduction and SDP Based Algorithms. 396-408

Ilya Baran, Erik D. Demaine, Mihai Patrascu:
Subquadratic Algorithms for 3SUM. 409-421
Jason D. Hartline, Vladlen Koltun:
Near-Optimal Pricing in Near-Linear Time. 422-431
Minkyoung Cho, David M. Mount:
Improved Approximation Bounds for Planar Point Pattern Matching. 432-443

Last update Fri May 24 19:55:04 2013 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page