Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase
Finding Spanning Trees In Strongly Connected Graphs With Per-Vertex Degree Constraints, Samuel Benjamin Chase
Computer Science and Software Engineering
In this project, I sought to develop and prove new algorithms to create spanning trees on general graphs with per-vertex degree constraints. This means that each vertex in the graph would have some additional value, a degree constraint d. For a spanning tree to be correct, every vertex vi in the spanning tree must have a degree exactly equal to a degree constraint di. This poses an additional constraint on what would otherwise be a trivial spanning tree problem. In this paper, two proofs related to my studies will be discussed and analyzed, leading to my algorithm …