Algorithms and Data Structures: 7th International Workshop, Wads 2001, Providence, Ri, Usa, August 8-10, 2001, Proceedings

by Wads 200 (2001 Providence, R. I.); Sack, J. R.; Tamassia, Roberto; Dehne, Frank; Dehne, Frank; Sack, J. R.

• ISBN13: 9783540424239
• ISBN10: 3540424237
• Format: Paperback
• Copyright: 2001-08-01
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 7th International Workshop on Algorithms and Data Structures, WADS 2001, held in Providence, RI, USA in August 2001. The 40 revised full papers presented were carefully reviewed and selected from a total of 89 submissions. Among the topics addressed are multiobjective optimization, computational graph theory, approximation, optimization, combinatorics, scheduling, Varanoi diagrams, packings, multi-party computation, polygons, searching, etc.

Table of Contents

Session 1 -- Invited Talk
Approximation of Multiobjective Optimization Problems	1	(1)
Mihalis Yannakakis
Session 2A
Optimal, Suboptimal, and Robust Algorithms for Proximity Graphs	2	(12)
Ferran Hurtado
Giuseppe Liotta
Henk Meijer
Optimal Mobius Transformations for Information Visualization and Meshing	14	(12)
Marshall Bern
David Eppstein
Session 2B
Using the Pseudo-Dimension to Analyze Approximation Algorithms for Integer Programming	26	(12)
Philip M. Long
On the Complexity of Scheduling Conditional Real-Time Code	38	(12)
Samarjit Chakraborty
Thomas Erlebach
Lothar Thiele
Session 3A
Time Responsive External Data Structures for Moving Points	50	(12)
Pankaj K. Agarwal
Lars Arge
Jan Vahrenhold
Voronoi Diagrams for Moving Disks and Applications	62	(13)
Menelaos I. Karavelas
Session 3B
Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover	75	(12)
Naomi Nishimura
Prabhakar Ragde
Dimitrios M. Thilikos
Deciding Clique-Width for Graphs of Bounded Tree-Width	87	(12)
Wolfgang Espelage
Frank Gurski
Egon Wanke
Session 4A
Complexity Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions	99	(12)
Vladlen Koltun
Optimization over Zonotopes and Training Support Vector Machines	111	(11)
Marshall Bern
David Eppstein
Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions	122	(13)
Pankaj K. Agarwal
Mark de Berg
Sariel Har-Peled
Mark H. Overmars
Micha Sharir
Jan Vahrenhold
Session 4B
Seller-Focused Algorithms for Online Auctioning	135	(13)
Amitabha Bagchi
Amitabh Chaudhary
Rahul Garg
Michael T. Goodrich
Vijay Kumar
Competitive Analysis of the LRFU Paging Algorithm	148	(7)
Edith Cohen
Haim Kaplan
Uri Zwick
Admission Control to Minimize Rejections	155	(10)
Avrim Blum
Adam Kalai
Jon Kleinberg
Session 5 -- Invited Talk
Secure Multi-party Computational Geometry	165	(15)
Mikhail J. Atallah
Wenliang Du
Session 6A
The Grid Placement Problem	180	(12)
Prosenjit Bose
Anil Maheshwari
Pat Morin
Jason Morrison
On the Reflexivity of Point Sets	192	(13)
Esther M. Arkin
Sandor P. Fekete
Ferran Hurtado
Joseph S.B. Mitchell
Marc Noy
Vera Sacristan
Saurabh Sethia
Session 6B
A 7/8 Approximation Algorithm for Metric Max TSP	205	(5)
Refael Hassin
Shlomi Rubinstein
Approximating Multi-objective Knapsack Problems	210	(12)
Thomas Erlebach
Hans Kellerer
Ulrich Pferschy
Session 7A
Visual Ranking of Link Structures	222	(12)
Ulrik Brandes
Sobine Cornelsen
A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs	234	(12)
Xin He
Session 7B
Short and Simple Labels for Small Distances and Other Functions	246	(12)
Haim Kaplan
Tova Milo
Fast Boolean Matrix Multiplication for Highly Clustered Data	258	(6)
Andreas Bjorklund
Andrzej Lingas
Session 8A
Partitioning Colored Point Sets into Monochromatic Parts	264	(12)
Adrian Dumitrescu
Janos Pach
The Analysis of a Probabilistic Approach to Nearest Neighbor Searching	276	(11)
Songrit Maneewongvatana
David M. Mount
I/O-Efficient Shortest Path Queries in Geometric Spanners	287	(13)
Anil Maheshwari
Michiel Smid
Norbert Zeh
Session 8B
Higher-Dimensional Packing with Order Constraints	300	(13)
Sandor P. Fekete
Ekkehard Kohler
Jurgen Teich
Bin Packing with Item Fragmentation	313	(12)
Nir Menakerman
Raphael Rom
Practical Approximation Algorithms for Separable Packing Linear Programs	325	(13)
Feodor F. Dragan
Andrew B. Kahng
Ion I. Mandoiu
Sudhakar Muddu
Alexander Zelikovsky
Session 9 -- Invited Talk
The Challenges of Delivering Content on the Internet	338	(1)
F. Thomson Leighton
Session 10A
Upward Embeddings and Orientations of Undirected Planar Graphs	339	(13)
Walter Didimo
Maurizio Pizzonia
An Approach for Mixed Upward Planarization	352	(13)
Markus Eiglsperger
Michael Kaufmann
Session 10B
A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study	365	(12)
David A. Bader
Bernard M.E. Moret
Mi Yan
Computing Phylogenetic Roots with Bounded Degrees and Errors	377	(12)
Zhi-Zhong Chen
Tao Jiang
Guo-Hui Lin
Session 11A
A Decomposition-Based Approach to Layered Manufacturing	389	(12)
Ivaylo Ilinkin
Ravi Janardan
Jayanth Majhi
Jorg Schwerdt
Michiel Smid
Ram Sriram
When Can You Fold a Map?	401	(13)
Esther M. Arkin
Michael A. Bender
Erik D. Demaine
Martin L. Demaine
Joseph S.B.Mitchell
Saurabh Sethia
Steven S. Skiena
Session 11B
Search Trees With Relaxed Balance and Near-Optimal Height	414	(12)
Rolf Fagerberg
Rune E.Jensen
Kim S. Larsen
Succinct Dynamic Data Structures	426	(12)
Rajeev Raman
Vnkatsh Raman
S. Srivivasa Rao
Session 12A
Optimal Algorithms for Two-Guard Walkability of Simple Polygons	438	(12)
Binay Bhattacharya
Ashish Mukhopadhyay
Firi Narasimhan
Movement Planning in the Presence if Flows	450	(12)
John Reif
Zheng Sun
Sesssion 12B
Small Maximal Independent Sets and Faster Extract Graph Coloring	462	(9)
David Eppstein
On External-Memory Planar Depth First Search	471	(12)
Lars Arge
Ilrich Meyer
Layra Toma
Norbert Zeh
Author Index	483