Maximum of k-th maximal spanning trees of a weighted graph
From MaRDI portal
Let T be a maximum-weight spanning tree in a connected weighted graph G and let P be an arbitrary spanning tree of G. The author proves that there exists a bijection b from \(A\setminus P\) onto \(P\setminus A\) such that for any edge a in \(A\setminus P\), \(P\setminus b(a)\cup a\) is a spanning tree of G whose weight is greater than or equal to that of P. This result is applied to some problems about spanning trees in a weighted graph.
Recommendations
- A solution to one of Kano's conjectures concerning k-th maximal spanning trees
- On the spanning trees of weighted graphs
- On the characterization of graphs with maximum number of spanning trees
- Heavy cycles and spanning trees with few leaves in weighted graphs
- Generating the maximum spanning trees of a weighted graph
Cites work
Cited in
(13)- A solution to one of Kano's conjectures concerning k-th maximal spanning trees
- On the spanning trees of weighted graphs
- Weight distribution of the bases of a binary matroid
- Multiplicative drift analysis
- Weight distribution of the bases of a matroid
- Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
- Partial trees in weighted graphs-I
- Kernelization for Maximum Leaf Spanning Tree with Positive Vertex Weights
- Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem
- On the spanning trees of weighted graphs
- Partitioning bispanning graphs into spanning trees
- 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: Maximum of k-th maximal spanning trees of a weighted graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1092057)
