On the spanning trees of weighted graphs
type: Item
instance of: scholarly article
title: On the spanning trees of weighted graphs
zbMATH Open document ID: 0780.05014
DOI: 10.1007/BF01305236
author: Ernst W. Mayr
author: C. Greg Plaxton
published in: Combinatorica
publication date: 1993-03-10T00:00:00Z
review text: The paper deals with several natural questions that arise when the spanning trees of a weighted graph are partitioned into the weight classes. The authors prove that every minimum-weight spanning tree is at most \(k-1\) edge swaps away from some representative of the \(k\)-th weight class, thereby settling a conjecture of \textit{M. Kano} [Combinatorica 7, 205-214 (1987; Zbl 0624.05027)]. In this latter paper, three more conjectures were posed for which the authors propose a stronger unified conjecture and confirm it in two non-trivial special cases. Finally, they consider the algorithmic complexity of the problem of generating a representative of the \(k\)-th weight class.
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 130616
zbMATH Keywords: spanning trees
zbMATH Keywords: weighted graph
zbMATH Keywords: algorithmic complexity
zbMATH Keywords: weight class
reviewed by: Martin Škoviera
MaRDI profile type: Publication
cites work: Systems of distinct representatives and linear algebra
cites work: Lower Bounds for Selection in X + Y and Other Multisets
cites work: Maximum of k-th maximal spanning trees of a weighted graph
cites work: Q5585020
cites work: On the shortest spanning subtree of a graph and the traveling salesman problem
cites work: A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
full work available at URL: https://doi.org/10.1007/bf01305236
OpenAlex ID: W2042401648
description: scientific article; zbMATH DE number 130616