A greedy algorithm for finding maximum spanning trees in infinite graphs

DOI10.1016/J.ORL.2022.10.004MaRDI QIDQ2102829zbMATH OpenOpenAlexFDO

Authors Christopher Thomas Ryan, Robert L. Smith

Publication date 12 December 2022

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2022.10.004

zbMATH Keywords

spanning treesinfinite-dimensional optimizationinfinite graphs

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Recommendations

• Minimum spanning trees in infinite graphs: theory and algorithms
• An O(m n) algorithm for the max+sum spanning tree problem
• An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem
• Two comments on minimum spanning trees
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Cites work

• scientific article; zbMATH DE number 1424324 (Why is no real title available?)
• scientific article; zbMATH DE number 3363579 (Why is no real title available?)
• scientific article; zbMATH DE number 7650919 (Why is no real title available?)
• A continuous-time network simplex algorithm
• 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
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems
• Conditions for the Existence of Planning Horizons
• Conditions for the discovery of solution horizons
• Graph theory
• Graph topologies induced by edge lengths
• Inverse optimization in minimum cost flow problems on countably infinite networks
• Minimum cost spanning tree games
• Network flows. Theory, algorithms, and applications.
• Note on Independence Functions
• On the History of the Minimum Spanning Tree Problem
• Solution and Forecast Horizons for Infinite-Horizon Nonhomogeneous Markov Decision Processes
• The Max-Flow Min-Cut theorem for countable networks
• The scaling limit of the minimum spanning tree of the complete graph
• Topological paths, cycles and spanning trees in infinite graphs
• Worst-case analysis of a new heuristic for the travelling salesman problem

Cited in

(3)

• Minimum spanning trees in infinite graphs: theory and algorithms
• Maximizing spanning trees in almost complete graphs
• Finding the \(N\) best vertices in an infinite weighted hypergraph

This page was built for publication: A greedy algorithm for finding maximum spanning trees in infinite graphs

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