An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem

DOI10.1016/0377-2217(92)90317-3zbMath0760.90088OpenAlexW2055114648MaRDI QIDQ1197938

S. Singh

Publication date: 16 January 1993

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(92)90317-3

zbMATH Keywords

minimum spanning tree problemgreedy algorithmsnetwork labelingone edge pass non-greedy algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (3)

On spanning tree problems with multiple objectives ⋮ Variable neighborhood search for the degree-constrained minimum spanning tree problem ⋮ Minimum-weight spanning tree algorithms. A survey and empirical study

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• Computational experience with minimum spanning tree algorithms
• The 2-quasi-greedy algorithm for cardinality constrained matroid bases
• Minimal spanning trees and partial sorting
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Priority queues with update and finding minimum spanning trees
• Computational Methods for Minimum Spanning Tree Algorithms
• Algorithm 613: Minimum Spanning Tree for Moderate Integer Weights
• Efficient algorithms for a family of matroid intersection problems
• New Polynomial Shortest Path Algorithms and Their Computational Attributes
• Multi-Terminal Network Flows
• On Finding and Updating Spanning Trees and Shortest Paths
• Implementing vehicle routing algorithms
• Finding Minimum Spanning Trees
• Enhancements Of Spanning Tree Labelling Procedures For Network Optimization
• On the History of the Minimum Spanning Tree Problem
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The traveling-salesman problem and minimum spanning trees: Part II
• Network reliability analysis: Part I
• Matroids and the greedy algorithm

This page was built for publication: An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem