Titlebook: Algorithms – ESA 2005; 13th Annual European Gerth Stølting Brodal,Stefano Leonardi Conference proceedings 2005 Springer-Verlag Berlin Heide

健忘症

Throttle

Heuristic Improvements for Computing Maximum Multicommodity Flow and Minimum Multicut, a graph. Through a series of improvements we are able to reduce the number of shortest path computations significantly. One key idea is to use the value of the best multicut encountered in the course of the algorithm. For almost all instances this multicut is significantly better than that computed by rounding the linear program.

蛛丝

,: Efficient and Exact Algorithms for Curves and Surfaces,ncy, correctness, completeness, clarity of the design, modularity, flexibility, and ease of use. We present the generic design and structure of the libraries, which currently compute arrangements of curves and curve segments of low algebraic degree, and boolean operations on polygons bounded by such segments.

companion

Designing Reliable Algorithms in Unreliable Memories,of even very few memory faults may jeopardize the correctness of the computational results. An algorithm is resilient to memory faults if, despite the corruption of some memory values before or during its execution, it is nevertheless able to get a correct output at least on the set of uncorrupted v

归功于

转换

Fearful Symmetries: Quantum Computing, Factoring, and Graph Isomorphism,t an adversary, physicists are brought up to believe in the benevolence of nature, and to believe that the answers to natural questions are often as simple—and as symmetric—as they possibly could be. Indeed, symmetry is intimately linked to every branch of physics, from classical conservation laws t

全等

解开

Online Routing in Faulty Meshes with Sub-linear Comparative Time and Traffic Ratio,t a flooding strategy like expanding ring search can route a message in the minimum number of steps . while it causes a traffic (i.e. the total number of messages) of .. For optimizing traffic a single-path strategy is optimal producing traffic ., where . is the perimeter length of the barriers form

STANT

exhilaration

Relax-and-Cut for Capacitated Network Design,m. The focus is on two types of valid inequalities, the cover inequalities and local cuts. We show how these inequalities can be considered in a Lagrangean relaxation without destroying the computationally simple structure of the subproblems. We present an extensive computational study on a large se