An Edge-Swap Heuristic for Finding Dense Spanning Trees

Mustafa Ozen, Hua Wang, Kai Wang, Demet Yalman

Research output: Contribution to journalArticlepeer-review

1 Downloads (Pure)

Abstract

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.

Original languageAmerican English
JournalTheory and Applications of Graphs
DOIs
StatePublished - Jan 1 2016

Disciplines

  • Discrete Mathematics and Combinatorics

Keywords

  • Spanning tree
  • edge-swap
  • heuristic

Fingerprint

Dive into the research topics of 'An Edge-Swap Heuristic for Finding Dense Spanning Trees'. Together they form a unique fingerprint.

Cite this