Algorithms – ESA 2005

Inhaltsverzeichnis

• 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 Coveringand 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.