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
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
