An algorithm for finding a matroid basis which maximizes the product of the weights of the elements
type: Item
instance of: scholarly article
title: An algorithm for finding a matroid basis which maximizes the product of the weights of the elements
zbMATH Open document ID: 0582.05017
DOI: 10.1007/BF01935363
published in: BIT
publication date: 1985-01-01T00:00:00Z
review text: This paper is devoted to a generalization to matroids of the problem of finding a spanning tree in an edge-weighted connected graph that maximizes the product of the weights of edges, where negative edge weights are allowed. As the main result, a polynomial time algorithm for the solution of this problem in the context of matroids is described.
reviewed by: J.Libicher
Mathematics Subject Classification ID: 05B35
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3931031
zbMATH Keywords: finding a spanning tree
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: matroids
author: T. I. Fenner
author: Alan Frieze
MaRDI profile type: Publication
cites work: Minimal ratio spanning trees
cites work: Matroids and the greedy algorithm
cites work: Efficient algorithms for a family of matroid intersection problems
cites work: Optimal assignments in an ordered set: An application of matroid theory
cites work: Q3048571
cites work: Combinatorial Optimization with Rational Objective Functions
cites work: Note on Independence Functions
cites work: Q5540285
full work available at URL: https://doi.org/10.1007/bf01935363
OpenAlex ID: W2007691782
description: scientific article; zbMATH DE number 3931031