Algorithms - ESA 2005

Inhalt

Designing Reliable Algorithms in Unreliable Memories.- From Balanced Graph Partitioning to Balanced Metric Labeling.- Fearful Symmetries: Quantum Computing, Factoring, and Graph Isomorphism.- Exploring an Unknown Graph Efficiently.- Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio.- Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut.- Relax-and-Cut for Capacitated Network Design.- On the Price of Anarchy and Stability of Correlated Equilibria of Linear Congestion Games,,.- The Complexity of Games on Highly Regular Graphs.- Computing Equilibrium Prices: Does Theory Meet Practice?.- Efficient Exact Algorithms on Planar Graphs: Exploiting Sphere Cut Branch Decompositions.- An Algorithm for the SAT Problem for Formulae of Linear Length.- Linear-Time Enumeration of Isolated Cliques.- Finding Shortest Non-separating and Non-contractible Cycles for Topologically Embedded Graphs.- Delineating Boundaries for Imprecise Regions.- Exacus: Efficient and Exact Algorithms for Curves and Surfaces.- Min Sum Clustering with Penalties.- Improved Approximation Algorithms for Metric Max TSP.- Unbalanced Graph Cuts.- Low Degree Connectivity in Ad-Hoc Networks.- 5-Regular Graphs are 3-Colorable with Positive Probability.- Optimal Integer Alphabetic Trees in Linear Time.- Predecessor Queries in Constant Time?.- An Algorithm for Node-Capacitated Ring Routing.- On Degree Constrained Shortest Paths.- A New Template for Solving p-Median Problems for Trees in Sub-quadratic Time.- Roll Cutting in the Curtain Industry.- Space Efficient Algorithms for the Burrows-Wheeler Backtransformation.- Cache-Oblivious Comparison-Based Algorithms on Multisets.- Oblivious vs. Distribution-Based Sorting: An Experimental Evaluation.- Allocating Memory in a Lock-Free Manner.- Generating Realistic Terrains with Higher-Order Delaunay Triangulations.- I/O-Efficient Construction of Constrained Delaunay Triangulations.- Convex Hull and Voronoi Diagram of Additively Weighted Points.- New Tools and Simpler Algorithms for Branchwidth.- Treewidth Lower Bounds with Brambles.- Minimal Interval Completions.- A 2-Approximation Algorithm for Sorting by Prefix Reversals.- Approximating the 2-Interval Pattern Problem.- A Loopless Gray Code for Minimal Signed-Binary Representations.- Efficient Approximation Schemes for Geometric Problems?.- Geometric Clustering to Minimize the Sum of Cluster Sizes.- Approximation Schemes for Minimum 2-Connected Spanning Subgraphs in Weighted Planar Graphs.- Packet Routing and Information Gathering in Lines, Rings and Trees.- Jitter Regulation for Multiple Streams.- Efficient c-Oriented Range Searching with DOP-Trees.- Matching Point Sets with Respect to the Earth Mover's Distance.- Small Stretch Spanners on Dynamic Graphs.- An Experimental Study of Algorithms for Fully Dynamic Transitive Closure.- Experimental Study of Geometric t-Spanners.- Highway Hierarchies Hasten Exact Shortest Path Queries.- Preemptive Scheduling of Independent Jobs on Identical Parallel Machines Subject to Migration Delays.- Fairness-Free Periodic Scheduling with Vacations.- Online Bin Packing with Cardinality Constraints.- Fast Monotone 3-Approximation Algorithm for Scheduling Related Machines.- Engineering Planar Separator Algorithms.- Stxxl: Standard Template Library for XXL Data Sets.- Negative Cycle Detection Problem.- An Optimal Algorithm for Querying Priced Information: Monotone Boolean Functions and Game Trees.- Online View Maintenance Under a Response-Time Constraint.- Online Primal-Dual Algorithms for Covering and Packing Problems.- Efficient Algorithms for Shared Backup Allocation in Networks with Partial Information.- Using Fractional Primal-Dual to Schedule Split Intervals with Demands.- An Approximation Algorithm for the Minimum Latency Set Cover Problem.- Workload-Optimal Histograms on Streams.- Finding Frequent Patterns in a String in Sublinear Time.- Online Occlusion Culling.- Shortest Paths in Matrix Multiplication Time.- Computing Common Intervals of K Permutations, with Applications to Modular Decomposition of Graphs.- Greedy Routing in Tree-Decomposed Graphs.- Making Chord Robust to Byzantine Attacks.- Bucket Game with Applications to Set Multicover and Dynamic Page Migration.- Bootstrapping a Hop-Optimal Network in the Weak Sensor Model.- Approximating Integer Quadratic Programs and MAXCUT in Subdense Graphs.- A Cutting Planes Algorithm Based Upon a Semidefinite Relaxation for the Quadratic Assignment Problem.- Approximation Complexity of min-max (Regret) Versions of Shortest Path, Spanning Tree, and Knapsack.- Robust Approximate Zeros.- Optimizing a 2D Function Satisfying Unimodality Properties.