Solution strategies for the spanning tree detection problem
For a given undirected, simple and connected graph G = (V, E) with edges associated with integer weights, the spanning tree detection problem (STDP) is to find, if one exists, the target weight value α of the spanning tree. There are numerous ways to solve this problem. Approximate algorithm is a gr...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Final Year Project |
| Language: | English |
| Published: |
2012
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/10356/49835 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | For a given undirected, simple and connected graph G = (V, E) with edges associated with integer weights, the spanning tree detection problem (STDP) is to find, if one exists, the target weight value α of the spanning tree. There are numerous ways to solve this problem. Approximate algorithm is a greedy method to construct an initial spanning tree (minimum or maximum spanning tree) quickly, and local search method can be applied to improve the weight of the tree towards the desired weight α. Heuristic algorithms can have different performance with regard to the various scheme of edge-selection (random decent scheme or steepest decent scheme). |
|---|