Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with minimum spanning trees:
TR04-089 | 26th October 2004
Ingo Wegener

Simulated Annealing Beats Metropolis in Combinatorial Optimization

The Metropolis algorithm is simulated annealing with a fixed temperature.Surprisingly enough, many problems cannot be solved more efficiently by simulated annealing than by the Metropolis algorithm with the best temperature. The problem of finding a natural example (artificial examples are known) where simulated annealing outperforms the Metropolis algorithm for all ... more >>>

TR06-143 | 15th November 2006
Frank Neumann, Carsten Witt

Ant Colony Optimization and the Minimum Spanning Tree Problem

Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>>

TR23-197 | 7th December 2023
Sepehr Assadi, Gillat Kol, Zhijun Zhang

Optimal Multi-Pass Lower Bounds for MST in Dynamic Streams

The seminal work of Ahn, Guha, and McGregor in 2012 introduced the graph sketching technique and used it to present the first streaming algorithms for various graph problems over dynamic streams with both insertions and deletions of edges. This includes algorithms for cut sparsification, spanners, matchings, and minimum spanning trees ... more >>>

ISSN 1433-8092 | Imprint