Algorithms and Data Structures

Optimization over k-set Polytopes and Efficient k-set Enumeration.- Line Simplification with Restricted Orientations.- The T-join Problem in Sparse Graphs: Applications to Phase Assignment Problem in VLSI Mask Layout.- Resizable Arrays in Optimal Time and Space.- Hash and Displace: Efficient Evaluation of Minimal Perfect Hash Functions.- Design and Analysis of Algorithms for Shared-Memory Multiprocessors.- On the Complexity of Orthogonal Compaction.- Optimizing Constrained Offset and Scaled Polygonal Annuli.- The Accomodating Function - A Generalization of the Competitive Ratio.- Performance Guarantees for the TSP with a Parameterized Triangle Inequality.- Robot Map Verification of a Graph World.- Searching Rectilinear Streets Completely.- General Multiprocessor Task Scheduling: Approximate Solutions in Linear Time.- The Lazy Bureaucrat Scheduling Problem.- Generating 3D Virtual Populations from Pictures of a Few Individuals.- Testing the Quality of Manufactured Balls.- On an Optimal Split Tree Problem.- Representing Trees of Higher Degree.- Indexing and Dictionary Matching with One Error (Extended Abstract).- New Results on Fault Tolerant Geometric Spanners.- Tiered Vectors: Efficient Dynamic Arrays for Rank-Based Sequences.- Go-With-The-Winners Heuristic.- 2-Point Site Voronoi Diagrams.- A Parallel Algorithm for Finding the Constrained Voronoi Diagram of Line Segments in the Plane.- Position-Independent Street Searching.- Approximation Algorithms for 3-D Common Substructure Identification in Drug and Protein Molecules.- A Tight Bound for ?-Skeleton of Minimum Weight Triangulations.- Rectilinear Static and Dynamic Discrete 2-center Problems.- Gene Trees and Species Trees: The Gene-Duplication Problem is Fixed-Parameter Tractable.- Efficient Web Searching UsingTemporal Factors.- Elastic Labels Around the Perimeter of a Map.- Optimal Facility Location under Various Distance Functions.- Thresholds for Sports Elimination Numbers: Algorithms and Complexity.- Dynamic Representations of Sparse Graphs.- Online Data Structures in External Memory.