Ontology highlight
ABSTRACT:
SUBMITTER: Li T
PROVIDER: S-EPMC5605090 | biostudies-literature | 2017
REPOSITORIES: biostudies-literature
Li Tao T Gao Yingqi Y Dong Qiankun Q Wang Hua H
PloS one 20170919 9
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 describ ...[more]