Solution strategies for the spanning tree detection problem

• Main Author: Ye, Min Thu.
• Other Authors: Low Chor Ping
• Format: Final Year Project
• Language: English
• Published: 2012
• Subjects: DRNTU::Engineering::Electrical and electronic engineering::Computer hardware, software and systems
• Online Access: http://hdl.handle.net/10356/49835
• Institution: Nanyang Technological University

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).