On the spanning trees of weighted graphs

DOI10.1007/BF01305236MaRDI QIDQ1204524zbMATH OpenOpenAlexFDO

Authors Ernst W. Mayr, C. Greg Plaxton

Publication date 10 March 1993

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01305236

zbMATH Keywords

algorithmic complexityspanning treesweight classweighted graph

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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.

Recommendations

• Weight distribution of the bases of a matroid
• A solution to one of Kano's conjectures concerning k-th maximal spanning trees
• Partitioning bispanning graphs into spanning trees
• Maximum of k-th maximal spanning trees of a weighted graph
• Partitioning bispanning graphs into spanning trees

Cites work

• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Lower Bounds for Selection in X + Y and Other Multisets
• Maximum of k-th maximal spanning trees of a weighted graph
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Systems of distinct representatives and linear algebra

Cited in

(19)

• Maximum of k-th maximal spanning trees of a weighted graph
• A solution to one of Kano's conjectures concerning k-th maximal spanning trees
• Finding the \(k\) smallest spanning trees
• Weight distribution of the bases of a binary matroid
• Weights of uniform spanning forests on nonunimodular transitive graphs
• Weight distribution of the bases of a matroid
• Computing strictly-second shortest paths
• Statuses and branch-weights of weighted trees
• Partitioning bispanning graphs into spanning trees
• The Weighted Spanning Tree Constraint Revisited
• TREE-WEIGHTED NEIGHBORS AND GEOMETRIC k SMALLEST SPANNING TREES
• Minimal spanning trees
• An analysis on recombination in multi-objective evolutionary optimization
• Finding the k smallest spanning trees
• On the spanning trees of weighted graphs
• Partitioning bispanning graphs into spanning trees
• Faster algorithm for second (s,t)-mincut and breaking quadratic barrier for dual edge sensitivity for (s,t)-mincut
• Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem

This page was built for publication: On the spanning trees of weighted graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1204524)