Anders Meng Hansen Abstract This report investigates heuristics for increasing edge connectivity in undirected graphs. Three simple heuristics, one metaheuristic and one advanced heuristic are considered. Four of the heuristics are tested with randomly generated graphs. The implementation and testing are done with MatLab. Results are analyzed. It is found that the heuristic using minimum spanning trees are the best of the four heuristics. It is also found that the running time of all 4 heuristics is very dependent on the computational efficiency of finding the minimum cut in a graph. Keywords Edge connectivity, Tabu search, Network design, minimum spanning tree, FSM. Type Master's thesis [Academic thesis] Year 2004 Publisher Informatics and Mathematical Modelling, Technical University of Denmark, DTU Address Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby Series IMM-Thesis-2004-61 Note Supervised by Prof. Jens Clausen Electronic version(s) [ps] BibTeX data [bibtex] IMM Group(s) Operations Research