A minimum spanning tree algorithm with inverse-Ackermann type complexity
From MaRDI portal
Publication:4406298
DOI10.1145/355541.355562zbMath1094.68606OpenAlexW2032841680WikidataQ55871138 ScholiaQ55871138MaRDI QIDQ4406298
Publication date: 25 June 2003
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/355541.355562
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
A new approach to all-pairs shortest paths on real-weighted graphs, Optimal per-edge processing times in the semi-streaming model, Improved algorithms for joint optimization of facility locations and network connections, Computing all efficient solutions of the biobjective minimum spanning tree problem, An Optimal Parallel Algorithm for Minimum Spanning Trees in Planar Graphs, Approximation Algorithms for a Network Design Problem, Proximity graphs inside large weighted graphs, Robust estimation of location and scatter by pruning the minimum spanning tree, Min‐sum controllable risk problems with concave risk functions of the same value range, Minimum shared‐power edge cut, On the probabilistic min spanning tree problem, Faster algorithm for optimum Steiner trees, Stable Approximation Algorithms for the Dynamic Broadcast Range-Assignment Problem, Coordination of multi-link spectrum handoff in multi-radio multi-hop cognitive networks, Relation-algebraic verification of Borůvka's minimum spanning tree algorithm, On symbolic OBDD-based algorithms for the minimum spanning tree problem, The saga of minimum spanning trees, Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs., Improved filtering for weighted circuit constraints, Triplet Merge Trees, Exact and approximate truthful mechanisms for the shortest paths tree problem, The path partition problem and related problems in bipartite graphs, A generalized approximation framework for fractional network flow and packing problems, An extension of the Christofides heuristic for the generalized multiple depot multiple traveling salesmen problem, Algorithms for topology-free and alignment network queries, A fast minimum spanning tree algorithm based on \(K\)-means, On Cartesian trees and range minimum queries, Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem, Ectropy of diversity measures for populations in Euclidean space, Improved algorithms for replacement paths problems in restricted graphs, On sorting, heaps, and minimum spanning trees, Fast reoptimization for the minimum spanning tree problem, Unnamed Item, Finding multi-objective supported efficient spanning trees, Min-max controllable risk problems, CENTRALITY AND PERIPHERALITY IN FILTERED GRAPHS FROM DYNAMICAL FINANCIAL CORRELATIONS, On Watershed Cuts and Thinnings, Design and Engineering of External Memory Traversal Algorithms for General Graphs, A selectable sloppy heap, A Generic Algorithm for Approximately Solving Stochastic Graph Optimization Problems, Multiple-edge-fault-tolerant approximate shortest-path trees, Unnamed Item, A Survey on Priority Queues, Robust Hierarchical Clustering for Directed Networks: An Axiomatic Approach, Lexicographic optimal homologous chains and applications to point cloud triangulations, Solving the Watchman Route Problem with Heuristic Search, The Inverse of Ackermann Function is Computable in Linear Time
