Degree sums and dense spanning trees

Tao Li, Yingqi Gao, Qiankun Dong and Hua Wang

PLOS ONE, 2017, vol. 12, issue 9, 1-12

Abstract: Finding dense spanning trees (DST) in unweighted graphs is a variation of the well studied minimum spanning tree problem (MST). We utilize established mathematical properties of extremal structures with the minimum sum of distances between vertices to formulate some general conditions on the sum of vertex degrees. We analyze the performance of various combinations of these degree sum conditions in finding dense spanning subtrees and apply our approach to practical examples. After briefly describing our algorithm we also show how it can be used on variations of DST, motivated by variations of MST. Our work provide some insights on the role of various degree sums in forming dense spanning trees and hopefully lay the foundation for finding fast algorithms or heuristics for related problems.

Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://journals.plos.org/plosone/article?id=10.1371/journal.pone.0184912 (text/html)
https://journals.plos.org/plosone/article/file?id= ... 84912&type=printable (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:plo:pone00:0184912

DOI: 10.1371/journal.pone.0184912

Access Statistics for this article

More articles in PLOS ONE from Public Library of Science
Bibliographic data for series maintained by plosone ().