Dehne / Sack / Tamassia Algorithms and Data Structures

7th International Workshop, WADS 2001 Providence, RI, USA, August 8-10, 2001 Proceedings
Erscheinungsjahr 2003
ISBN: 978-3-540-44634-7
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 2125, 492 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Dehne, Frank

Sack, Jörg-Rüdiger

Tamassia, Roberto

Inhaltsverzeichnis

Session 1 - Invited Talk.- Approximation of Multiobjective Optimization Problems.- Session 2A.- Optimal, Suboptimal, and Robust Algorithms for Proximity Graphs.- Optimal Möbius Transformations for Information Visualization and Meshing.- Session 2B.- Using the Pseudo-Dimension to Analyze Approximation Algorithms for Integer Programming.- On the Complexity of Scheduling Conditional Real-Time Code.- Session 3A.- Time Responsive External Data Structures for Moving Points.- Voronoi Diagrams for Moving Disks and Applications.- Session 3B.- Fast Fixed-Parameter Tractable Algorithms for Nontrivial Generalizations of Vertex Cover.- Deciding Clique-Width for Graphs of Bounded Tree-Width.- Session 4A.- Complexity Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions.- Optimization over Zonotopes and Training Support Vector Machines.- Reporting Intersecting Pairs of Polytopes in Two and Three Dimensions.- Session 4B.- Seller-Focused Algorithms for Online Auctioning.- Competitive Analysis of the LRFU Paging Algorithm.- Admission Control to Minimize Rejections.- Session 5 - Invited Talk.- Secure Multi-party Computational Geometry.- Session 6A.- The Grid Placement Problem.- On the Reflexivity of Point Sets.- Session 6B.- A 7/8-Approximation Algorithm for Metric Max TSP.- Approximating Multi-objective Knapsack Problems.- Session 7A.- Visual Ranking of Link Structures.- A Simple Linear Time Algorithm for Proper Box Rectangular Drawings of Plane Graphs.- Session 7B.- Short and Simple Labels for Small Distances and Other Functions.- Fast Boolean Matrix Multiplication for Highly Clustered Data.- Session 8A.- Partitioning Colored Point Sets into Monochromatic Parts.- The Analysis of a Probabilistic Approach to Nearest Neighbor Searching.- I/O-Efficient Shortest PathQueries in Geometric Spanners.- Session 8B.- Higher-Dimensional Packing with Order Constraints.- Bin Packing with Item Fragmentation.- Practical Approximation Algorithms for Separable Packing Linear Programs.- Session 9 - Invited Talk.- The Challenges of Delivering Content on the Internet.- Session 10A.- Upward Embeddings and Orientations of Undirected Planar Graphs.- An Approach for Mixed Upward Planarization.- Session 10B.- A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study.- Computing Phylogenetic Roots with Bounded Degrees and Errors.- Session 11A.- A Decomposition-Based Approach to Layered Manufacturing.- When Can You Fold a Map?.- Session 11B.- Search Trees with Relaxed Balance and Near-Optimal Height.- Succinct Dynamic Data Structures.- Session 12A.- Optimal Algorithms for Two-Guard Walkability of Simple Polygons.- Movement Planning in the Presence of Flows.- Session 12B.- Small Maximal Independent Sets and Faster Exact Graph Coloring.- On External-Memory Planar Depth First Search.