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

spanning treesweighted graphalgorithmic complexityweight class

Mathematics Subject Classification ID

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

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

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• 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

(18)

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

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)