An optimal minimum spanning tree algorithm
From MaRDI portal
Publication:3196633
DOI10.1145/505241.505243zbMath1323.05124OpenAlexW1965525854WikidataQ55878913 ScholiaQ55878913MaRDI QIDQ3196633
Vijaya Ramachandran, Seth Pettie
Publication date: 30 October 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.110.7670
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges, A new approach to all-pairs shortest paths on real-weighted graphs, Optimal per-edge processing times in the semi-streaming model, Minimum spanning paths and Hausdorff distance in finite ultrametric spaces, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, A new approach for the multiobjective minimum spanning tree, The reduction of computation times of upper and lower tolerances for selected combinatorial optimization problems, Proximity graphs inside large weighted graphs, Tight bounds for distributed minimum-weight spanning tree verification, Cost optimized design for the local wind turbine grid of an onshore wind farm, Minimum shared‐power edge cut, Faster algorithms for largest empty rectangles and boxes, On symbolic OBDD-based algorithms for the minimum spanning tree problem, A class of multivariate distribution-free tests of independence based on graphs, Amplification and Derandomization without Slowdown, The saga of minimum spanning trees, Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs., Research on solution space of bipartite graph vertex-cover by maximum matchings, PORA: a Physarum-inspired obstacle-avoiding routing algorithm for integrated circuit design, On Cartesian trees and range minimum queries, Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem, Algorithms for Euclidean Degree Bounded Spanning Tree Problems, Design and Engineering of External Memory Traversal Algorithms for General Graphs, Combinatorial optimization in system configuration design, Stability of Networks in Stretchable Graphs, A Survey on Priority Queues, Efficient computation of tolerances in the sensitivity analysis of combinatorial bottleneck problems
