An algorithm for finding a matroid basis which maximizes the product of the weights of the elements |
| |
| Authors: | T I Fenner A M Frieze |
| |
| Institution: | (1) Department of Computer Science, Birkbeck College, University of London, Malet Street, WC1E 7HX London, England;(2) Department of Computer Science and Statistics, Queen Mary College, University of London, E1 4NS London, England |
| |
| Abstract: | Consider the problem of finding a spanning tree in an edge-weighted connected graph that maximizes the product of its edge weights, where negative edge weights are allowed. We generalize this problem to matroids and give a polynomial time algorithm for its solution. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
