Beta 1


Title Grafsammenhæng i netværk
Author Hansen, Anders Meng
Supervisor Clausen, Jens (Institut for Informatik og Matematisk Modellering, Danmarks Tekniske Universitet, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2004
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.
Imprint Institut for Informatik og Matematisk Modellering, Danmarks Tekniske Universitet, DTU : DK-2800 Kgs. Lyngby, Denmark
Keywords Edge connectivity; Tabu search; Network design; minimum spanning tree; FSM.
Fulltext
Derived PDF imm3266.pdf (0.31 MB)
Original Postscript imm3266.ps (0.37 MB)
Admin Creation date: 2006-06-22    Update date: 2012-12-21    Source: dtu    ID: 154760    Original MXD