A greedy algorithm for finding maximum spanning trees in infinite graphs |
| |
| Institution: | 1. UBC Sauder School of Business, 2053 Main Mall, Vancouver, British Columbia, V6M 3W2, Canada;2. University of Michigan, Industrial and Operations Engineering, 1205 Beal Ave., Ann Arbor, MI, 48109-2117, United States of America |
| |
| Abstract: | In finite graphs, greedy algorithms are used to find minimum spanning trees (MinST) and maximum spanning trees (MaxST). In infinite graphs, we illustrate a general class of problems where a greedy approach discovers a MaxST while a MinST may be unreachable. Our algorithm is a natural extension of Prim's to infinite graphs with summable and strictly positive edge weights, producing a sequence of finite trees that converge to a MaxST. |
| |
| Keywords: | Spanning trees Infinite graphs Infinite-dimensional optimization |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
