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