On the spanning trees of weighted graphs

DOI10.1007/BF01305236zbMath0780.05014OpenAlexW2042401648MaRDI QIDQ1204524

C. Greg Plaxton, Ernst W. Mayr

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 complexityweighted graphspanning treesweight class

Mathematics Subject Classification ID

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

Related Items (10)

Computing strictly-second shortest paths ⋮ Finding the k smallest spanning trees ⋮ Reconfiguration of dominating sets ⋮ 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 ⋮ Partitioning bispanning graphs into spanning trees ⋮ An analysis on recombination in multi-objective evolutionary optimization ⋮ Finding the \(k\) smallest spanning trees ⋮ Weight distribution of the bases of a matroid ⋮ Weight distribution of the bases of a binary matroid

Cites Work

• On the shortest spanning subtree of a graph and the traveling salesman problem
• Maximum of k-th maximal spanning trees of a weighted graph
• Lower Bounds for Selection in X + Y and Other Multisets
• Systems of distinct representatives and linear algebra
• A Procedure for Computing the K Best Solutions to Discrete Optimization Problems and Its Application to the Shortest Path Problem
• Unnamed Item

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