Minimum spanning trees in infinite graphs: theory and algorithms

DOI10.1137/23M157627XMaRDI QIDQ6622744zbMATH OpenFDO

Authors Christopher Thomas Ryan, Robert L. Smith, Marina Epelman

Publication date 22 October 2024

Published in SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/23M157627X

zbMATH Keywords

infinite graphsinfinite-dimensional optimizationminimum spanning trees

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming involving graphs or networks (90C35) Programming in abstract spaces (90C48)

Recommendations

• Minimal spanning trees on infinite sets
• Successive minimum spanning trees
• A greedy algorithm for finding maximum spanning trees in infinite graphs
• scientific article; zbMATH DE number 1670813
• An optimal minimum spanning tree algorithm

Cites work

• A continuous-time network simplex algorithm
• A greedy algorithm for finding maximum spanning trees in infinite graphs
• A simplex algorithm for minimum-cost network-flow problems in infinite networks
• A simplex method for uncapacitated pure-supply infinite network flow problems
• Asymptotics for Euclidean minimal spanning trees on random points
• Axioms for infinite matroids
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Convergence of selections with applications in optimization
• Duality in convex minimum cost flow problems on infinite networks and hypernetworks
• Duality in Countably Infinite Monotropic Programs
• Extreme point characterizations for infinite network flow problems
• scientific article; zbMATH DE number 5776838 (Why is no real title available?)
• scientific article; zbMATH DE number 38300 (Why is no real title available?)
• scientific article; zbMATH DE number 1461253 (Why is no real title available?)
• scientific article; zbMATH DE number 3363579 (Why is no real title available?)
• Infinite dimensional analysis. A hitchhiker's guide.
• Inverse optimization in minimum cost flow problems on countably infinite networks
• Minimal spanning forests
• Minimum cost spanning tree games
• Network flows. Theory, algorithms, and applications.
• On the History of the Minimum Spanning Tree Problem
• Percolation and minimal spanning forests in infinite graphs
• The Max-Flow Min-Cut theorem for countable networks
• The scaling limit of the minimum spanning tree of the complete graph

Cited in

(1)

• A greedy algorithm for finding maximum spanning trees in infinite graphs

This page was built for publication: Minimum spanning trees in infinite graphs: theory and algorithms

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