Skip to main content
An Edge-Swap Heuristic for Finding Dense Spanning Trees
Theory and Applications of Graphs
  • Mustafa Ozen, Bogazici University
  • Hua Wang, Georgia Southern University
  • Kai Wang, Georgia Southern University
  • Demet Yalman, Bogazici University
Publication Date

Finding spanning trees under various restrictions has been an interesting question to researchers. A "dense" tree, from a graph theoretical point of view, has small total distances between vertices and large number of substructures. In this note, the "density" of a spanning tree is conveniently measured by the weight of a tree (defined as the sum of products of adjacent vertex degrees). By utilizing established conditions and relations between trees with the minimum total distance or maximum number of sub-trees, an edge-swap heuristic for generating "dense" spanning trees is presented. Computational results are presented for randomly generated graphs and specific examples from applications.

Creative Commons License
Creative Commons Attribution 4.0
Citation Information
Mustafa Ozen, Hua Wang, Kai Wang and Demet Yalman. "An Edge-Swap Heuristic for Finding Dense Spanning Trees" (2016)
Available at: