An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
From MaRDI portal
Publication:1218265
DOI10.1016/0020-0190(75)90056-3zbMath0307.68028OpenAlexW1973942323MaRDI QIDQ1218265
Publication date: 1975
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(75)90056-3
Related Items (32)
The hybrid spanning tree problem ⋮ Efficient algorithms for finding minimum spanning trees in undirected and directed graphs ⋮ Chance constrained bottleneck spanning tree problem ⋮ A matroid algorithm and its application to the efficient solution of two optimization problems on graphs ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ On the probabilistic min spanning tree problem ⋮ An approximation algorithm for the clustered path travelling salesman problem ⋮ A fast algorithm for Steiner trees ⋮ Finding minimal spanning trees in a Euclidean coordinate space ⋮ Relation-algebraic verification of Borůvka's minimum spanning tree algorithm ⋮ On the relationship between the biconnectivity augmentation and traveling salesman problems ⋮ An optimal PRAM algorithm for a spanning tree on trapezoid graphs. ⋮ Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs. ⋮ An O(log n) parallel algorithm for constructing a spanning tree on permutation graphs ⋮ An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem ⋮ Edge-disjoint spanning trees and the number of maximum state circles of a graph ⋮ A fast minimum spanning tree algorithm based on \(K\)-means ⋮ Huffman coding with non-sorted frequencies ⋮ An \(O(\log m)\) parallel algorithm for the minimum spanning tree problem ⋮ Priority queues with update and finding minimum spanning trees ⋮ Fast reoptimization for the minimum spanning tree problem ⋮ Minimum-weight spanning tree algorithms. A survey and empirical study ⋮ A probabilistic minimum spanning tree algorithm ⋮ The Min-Max Spanning Tree Problem and some extensions ⋮ Optimal one-page tree embeddings in linear time ⋮ Use of matroid theory in operations research, circuits and systems theory ⋮ Combinatorial optimization in system configuration design ⋮ Constrained spanning trees and the traveling salesman problem ⋮ The stochastic bottleneck linear programming problem ⋮ Polynomial testing of the query Is \(a^ b\geq c^ d?\) with application to finding a minimal cost reliability ratio spanning tree ⋮ Linear verification for spanning trees ⋮ Optimal vertex ordering of graphs
Cites Work
This page was built for publication: An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
