A greedy algorithm for finding maximum spanning trees in infinite graphs

DOI10.1016/J.ORL.2022.10.004OpenAlexW4305072505MaRDI QIDQ2102829FDOQ2102829

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

Recommendations

• Minimum spanning trees in infinite graphs: theory and algorithms
• An \(O(m\log 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

zbMATH Keywords

spanning treesinfinite-dimensional optimizationinfinite graphs

Mathematics Subject Classification ID

Operations research, mathematical programming (90-XX)

Cites Work

• Network flows. Theory, algorithms, and applications.
• Graph theory
• Asymptotics for Euclidean minimal spanning trees on random points
• Minimum cost spanning tree games
• Topological paths, cycles and spanning trees in infinite graphs
• A simplex algorithm for minimum-cost network-flow problems in infinite networks
• Worst-case analysis of a new heuristic for the travelling salesman problem
• Title not available (Why is that?)
• On the History of the Minimum Spanning Tree Problem
• Solution and Forecast Horizons for Infinite-Horizon Nonhomogeneous Markov Decision Processes
• A continuous-time network simplex algorithm
• Graph topologies induced by edge lengths
• The Max-Flow Min-Cut theorem for countable networks
• Conditions for the discovery of solution horizons
• Conditions for the Existence of Planning Horizons
• Title not available (Why is that?)
• The scaling limit of the minimum spanning tree of the complete graph
• Concepts of Forecast and Decision Horizons: Applications to Dynamic Stochastic Optimization Problems
• A simplex method for uncapacitated pure-supply infinite network flow problems
• Note on Independence Functions
• Inverse optimization in minimum cost flow problems on countably infinite networks
• Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems
• Title not available (Why is that?)

Cited In (3)

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

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)