Dehne / Sack / Toth Algorithms and Data Structures

11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings
2009
ISBN: 978-3-642-03367-4
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, Band 5664, 580 Seiten, eBook

Reihe: Lecture Notes in Computer Science

Zielgruppe

Research

Autoren/Hrsg.

Dehne, Frank

Sack, Jörg-Rüdiger

Toth, Csaba D.

Inhaltsverzeichnis

On the Power of the Semi-Separated Pair Decomposition.- Plane Graphs with Parity Constraints.- Straight-Line Rectangular Drawings of Clustered Graphs.- Online Priority Steiner Tree Problems.- Connect the Dot: Computing Feed-Links with Minimum Dilation.- Minimal Locked Trees.- Approximating Transitive Reductions for Directed Networks.- 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2.- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing.- A Distribution-Sensitive Dictionary with Low Space Overhead.- A Comparison of Performance Measures for Online Algorithms.- Delaunay Triangulation of Imprecise Points Simplified and Extended.- An Improved SAT Algorithm in Terms of Formula Length.- Shortest Path Problems on a Polyhedral Surface.- Approximation Algorithms for Buy-at-Bulk Geometric Network Design.- Rank-Sensitive Priority Queues.- Algorithms Meet Art, Puzzles, and Magic.- Skip-Splay: Toward Achieving the Unified Bound in the BST Model.- Drawing Graphs with Right Angle Crossings.- Finding a Hausdorff Core of a Polygon: On Convex Polygon Containment with Bounded Hausdorff Distance.- Efficient Construction of Near-Optimal Binary and Multiway Search Trees.- On the Approximability of Geometric and Geographic Generalization and the Min-Max Bin Covering Problem.- On Reconfiguration of Disks in the Plane and Related Problems.- Orientation-Constrained Rectangular Layouts.- The h-Index of a Graph and Its Application to Dynamic Subgraph Statistics.- Optimal Embedding into Star Metrics.- Online Square Packing.- Worst-Case Optimal Adaptive Prefix Coding.- New Results on Visibility in Simple Polygons.- Dynamic Graph Clustering Using Minimum-Cut Trees.- Rank-Balanced Trees.- Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments.- Reconfiguration of List Edge-Colorings in a Graph.- The Simultaneous Representation Problem for Chordal, Comparability and Permutation Graphs.- Two for One: Tight Approximation of 2D Bin Packing.- Fault Tolerant External Memory Algorithms.- Inspecting a Set of Strips Optimally.- A Pseudopolynomial Algorithm for Alexandrov’s Theorem.- A Scheme for Computing Minimum Covers within Simple Regions.- Better Approximation Algorithms for the Maximum Internal Spanning Tree Problem.- Two Approximation Algorithms for ATSP with Strengthened Triangle Inequality.- Streaming Embeddings with Slack.- Computing the Implicit Voronoi Diagram in Triple Precision.- Efficient Approximation of Combinatorial Problems by Moderately Exponential Algorithms.- Integer Programming: Optimization and Evaluation Are Equivalent.- Resolving Loads with Positive Interior Stresses.- On Making Directed Graphs Transitive.- Bit-Parallel Tree Pattern Matching Algorithms for Unordered Labeled Trees.- Compact and Low Delay Routing Labeling Scheme for Unit Disk Graphs.