A solution to the problem of finding an optimal spanning tree using the computer
Date of Publication
1991
Document Type
Bachelor's Thesis
Degree Name
Bachelor of Science in Applied Mathematics
College
College of Science
Department/Unit
Mathematics and Statistics
Abstract/Summary
This paper presents two algorithms in finding an optimal (minimum or maximum) spanning tree of a given weighted, simple, connected graph G on n vertices, where 1 n 10. The algorithms, which are a version of Kruskal's and Prim's algorithms combined, are coded into two programming languages namely CLIPPER and TURBO C. A detailed proof of the algorithm for finding a minimum spanning tree of G is provided. The researchers likewise presented a variation of Kruskal's algorithm, that is, finding optimal spanning trees with arbitrarily fixed edges.
Abstract Format
html
Language
English
Format
Accession Number
TU05691
Shelf Location
Archives, The Learning Commons, 12F, Henry Sy Sr. Hall
Physical Description
71 numb. leaves
Keywords
Trees (Graph theory); Programming (Mathematics); Problem solving
Recommended Citation
Adriano, J. T., & Labayen, R. L. (1991). A solution to the problem of finding an optimal spanning tree using the computer. Retrieved from https://animorepository.dlsu.edu.ph/etd_bachelors/15943
