Please use this identifier to cite or link to this item:
Title: Solution strategies for the spanning tree detection problem
Authors: Ye, Min Thu.
Keywords: DRNTU::Engineering::Electrical and electronic engineering::Computer hardware, software and systems
Issue Date: 2012
Abstract: 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).
Rights: Nanyang Technological University
Fulltext Permission: restricted
Fulltext Availability: With Fulltext
Appears in Collections:EEE Student Reports (FYP/IA/PA/PI)

Files in This Item:
File Description SizeFormat 
  Restricted Access
1.23 MBAdobe PDFView/Open

Page view(s)

Updated on Nov 29, 2020


Updated on Nov 29, 2020

Google ScholarTM


Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.