Algorithms - ESA 2005: 13th Annual European Symposium, Palma de Mallorca, Spain, October 3-6, 2005, Proceedings

ISBN-13: 9783540291183 / Angielski / Miękka / 2005 / 928 str.

Gerth Stolting Brodal; Stefano Leonardi

Opis

Constitutes the proceedings of the 13th Annual European Symposium on Algorithms, ESA 2005, in the context of the combined conference ALGO 2005. The papers presented in this book address the issues in algorithmics reaching from design and mathematical issues over applications in various fields up to engineering and analysis of algorithms.

Spis treści

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.