Paper Info
Title
Maximizing the Number of Spanning Trees in a Connected Graph.
Abstract
We study the problem of maximizing the number of spanning trees in a connected graph with n vertices and m edges, by adding at most k edges from a given set of q candidate edges, a problem that has applications in many domains. We give both algorithmic and hardness results for this problem: 1) We give a greedy algorithm that obtains an approximation ratio of (1 - 1/e - ∈) in the exponent of the nu...
Year
DOI
Venue
2018
10.1109/TIT.2019.2940263
IEEE Transactions on Information Theory
Keywords
DocType
Volume
Approximation algorithms,Reliability,Simultaneous localization and mapping,Resistance,Communication networks,Heuristic algorithms,Greedy algorithms
Journal
66
Issue
ISSN
Citations 
2
0018-9448
0
PageRank 
References 
Authors
0.34
23
4
Name
Order
Citations
PageRank
Huan Li1184.60
Stacy Patterson235130.68
Yuhao Yi3226.91
Zhongzhi Zhang48522.02