The saga of minimum spanning trees (Q458468): Difference between revisions

@@ Property / describes a project that uses @@
+Find
@@ Property / describes a project that uses: Find / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+Haskell
@@ Property / describes a project that uses: Haskell / rank @@
+Normal rank
@@ Property / describes a project that uses @@
+Quicksort
@@ Property / describes a project that uses: Quicksort / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.cosrev.2008.10.002
+Normal rank
@@ Property / OpenAlex ID @@
+W1981755382
@@ Property / OpenAlex ID: W1981755382 / rank @@
+Normal rank
@@ Property / cites work @@
+On the History of the Minimum Spanning Tree Problem
+Normal rank
@@ Property / cites work @@
+Q4231478
@@ Property / cites work: Q4231478 / rank @@
+Normal rank
@@ Property / cites work @@
+Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
+Normal rank
@@ Property / cites work @@
+Fibonacci heaps and their uses in improved network optimization algorithms
+Normal rank
@@ Property / cites work @@
+A minimum spanning tree algorithm with inverse-Ackermann type complexity
+Normal rank
@@ Property / cites work @@
+An optimal minimum spanning tree algorithm
@@ Property / cites work: An optimal minimum spanning tree algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+Q3707420
@@ Property / cites work: Q3707420 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3135082
@@ Property / cites work: Q3135082 / rank @@
+Normal rank
@@ Property / cites work @@
+Sur la liaison et la division des points d'un ensemble fini
+Normal rank
@@ Property / cites work @@
+A note on two problems in connexion with graphs
@@ Property / cites work: A note on two problems in connexion with graphs / rank @@
+Normal rank
@@ Property / cites work @@
+On the shortest spanning subtree of a graph and the traveling salesman problem
+Normal rank
@@ Property / cites work @@
+Efficiency of a Good But Not Linear Set Union Algorithm
+Normal rank
@@ Property / cites work @@
+Finding Minimum Spanning Trees
@@ Property / cites work: Finding Minimum Spanning Trees / rank @@
+Normal rank
@@ Property / cites work @@
+Q5315023
@@ Property / cites work: Q5315023 / rank @@
+Normal rank
@@ Property / cites work @@
+The minimum spanning tree problem on a planar graph
+Normal rank
@@ Property / cites work @@
+Q4133134
@@ Property / cites work: Q4133134 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4471360
@@ Property / cites work: Q4471360 / rank @@
+Normal rank
@@ Property / cites work @@
+Deterministic Dictionaries
@@ Property / cites work: Deterministic Dictionaries / rank @@
+Normal rank
@@ Property / cites work @@
+Q4398780
@@ Property / cites work: Q4398780 / rank @@
+Normal rank
@@ Property / cites work @@
+On the succinct representation of graphs
@@ Property / cites work: On the succinct representation of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4856179
@@ Property / cites work: Q4856179 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4414308
@@ Property / cites work: Q4414308 / rank @@
+Normal rank
@@ Property / cites work @@
+Purely Functional Data Structures
@@ Property / cites work: Purely Functional Data Structures / rank @@
+Normal rank
@@ Property / cites work @@
+On an algorithm of Zemlyachenko for subtree isomorphism
+Normal rank
@@ Property / cites work @@
+Nearest common ancestors: a survey and a new algorithm for a distributed environment
+Normal rank
@@ Property / cites work @@
+Q4542546
@@ Property / cites work: Q4542546 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph Isomorphism is in SPP
@@ Property / cites work: Graph Isomorphism is in SPP / rank @@
+Normal rank
@@ Property / cites work @@
+Preserving order in a forest in less than logarithmic time and linear space
+Normal rank
@@ Property / cites work @@
+Surpassing the information theoretic bound with fusion trees
+Normal rank
@@ Property / cites work @@
+Deterministic sorting in             <i>O</i>             (             <i>n</i>             log log             <i>n</i>             ) time and linear space
+Normal rank
@@ Property / cites work @@
+Linear-Time Ranking of Permutations
@@ Property / cites work: Linear-Time Ranking of Permutations / rank @@
+Normal rank
@@ Property / cites work @@
+Undirected single-source shortest paths with positive integer weights in linear time
+Normal rank
@@ Property / cites work @@
+Integer priority queues with decrease key in constant time and the single source shortest paths problem
+Normal rank
@@ Property / cites work @@
+Q2754134
@@ Property / cites work: Q2754134 / rank @@
+Normal rank
@@ Property / cites work @@
+Trans-dichotomous algorithms for minimum spanning trees and shortest paths
+Normal rank
@@ Property / cites work @@
+Q4508365
@@ Property / cites work: Q4508365 / rank @@
+Normal rank
@@ Property / cites work @@
+Fusion trees can be implemented with \(AC^0\) instructions only
+Normal rank
@@ Property / cites work @@
+Graph minor theory
@@ Property / cites work: Graph minor theory / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. XX: Wagner's conjecture
@@ Property / cites work: Graph minors. XX: Wagner's conjecture / rank @@
+Normal rank
@@ Property / cites work @@
+Homomorphieeigenschaften und mittlere Kantendichte von Graphen
+Normal rank
@@ Property / cites work @@
+Lower bound of the Hadwiger number of graphs by their average degree
+Normal rank
@@ Property / cites work @@
+An extremal function for contractions of graphs
@@ Property / cites work: An extremal function for contractions of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q3435477
@@ Property / cites work: Q3435477 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2747613
@@ Property / cites work: Q2747613 / rank @@
+Normal rank
@@ Property / cites work @@
+Q2766845
@@ Property / cites work: Q2766845 / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
+Normal rank
@@ Property / cites work @@
+Linear verification for spanning trees
@@ Property / cites work: Linear verification for spanning trees / rank @@
+Normal rank
@@ Property / cites work @@
+Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
+Normal rank
@@ Property / cites work @@
+A simpler minimum spanning tree verification algorithm
+Normal rank
@@ Property / cites work @@
+Multi-Terminal Network Flows
@@ Property / cites work: Multi-Terminal Network Flows / rank @@
+Normal rank
@@ Property / cites work @@
+An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
+Normal rank
@@ Property / cites work @@
+A data structure for dynamic trees
@@ Property / cites work: A data structure for dynamic trees / rank @@
+Normal rank
@@ Property / cites work @@
+Q5624995
@@ Property / cites work: Q5624995 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast Algorithms for Finding Nearest Common Ancestors
+Normal rank
@@ Property / cites work @@
+An inverse-Ackermann type lower bound for online minimum spanning tree verification
+Normal rank
@@ Property / cites work @@
+A randomized linear-time algorithm to find minimum spanning trees
+Normal rank
@@ Property / cites work @@
+A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
+Normal rank
@@ Property / cites work @@
+Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees
+Normal rank
@@ Property / cites work @@
+The soft heap
@@ Property / cites work: The soft heap / rank @@
+Normal rank
@@ Property / cites work @@
+A data structure for manipulating priority queues
@@ Property / cites work: A data structure for manipulating priority queues / rank @@
+Normal rank
@@ Property / cites work @@
+Time bounds for selection
@@ Property / cites work: Time bounds for selection / rank @@
+Normal rank
@@ Property / cites work @@
+Quicksort
@@ Property / cites work: Quicksort / rank @@
+Normal rank
@@ Property / cites work @@
+Q4829006
@@ Property / cites work: Q4829006 / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized fully dynamic graph algorithms with polylogarithmic time per operation
+Normal rank
@@ Property / cites work @@
+Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
+Normal rank
@@ Property / cites work @@
+Sparsification—a technique for speeding up dynamic graph algorithms
+Normal rank
@@ Property / cites work @@
+Maintaining minimum spanning trees in dynamic graphs
+Normal rank
@@ Property / cites work @@
+Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
+Normal rank
@@ Property / cites work @@
+Lower bounds for fully dynamic connectivity problems in graphs
+Normal rank
@@ Property / cites work @@
+Near-optimal fully-dynamic graph connectivity
@@ Property / cites work: Near-optimal fully-dynamic graph connectivity / rank @@
+Normal rank
@@ Property / cites work @@
+An Algorithm for Finding <i>K</i> Minimum Spanning Trees
+Normal rank
@@ Property / cites work @@
+Finding the \(k\) smallest spanning trees
@@ Property / cites work: Finding the \(k\) smallest spanning trees / rank @@
+Normal rank
@@ Property / cites work @@
+Applications of Path Compression on Balanced Trees
+Normal rank
@@ Property / cites work @@
+Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
+Normal rank
@@ Property / cites work @@
+Floats, Integers, and Single Source Shortest Paths
+Normal rank
@@ Property / cites work @@
+A sweepline algorithm for Voronoi diagrams
@@ Property / cites work: A sweepline algorithm for Voronoi diagrams / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient minimum spanning tree construction with Delaynay triangulation
+Normal rank
@@ Property / cites work @@
+Q4945509
@@ Property / cites work: Q4945509 / rank @@
+Normal rank
@@ Property / cites work @@
+Probability theory of classical Euclidean optimization problems
+Normal rank
@@ Property / cites work @@
+Vojtěch Jarník's work in combinatorial optimization
+Normal rank
@@ Property / cites work @@
+The Complexity of Computing Steiner Minimal Trees
@@ Property / cites work: The Complexity of Computing Steiner Minimal Trees / rank @@
+Normal rank
@@ Property / cites work @@
+The Rectilinear Steiner Tree Problem is $NP$-Complete
+Normal rank
@@ Property / cites work @@
+A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
+Normal rank
@@ Property / cites work @@
+Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
+Normal rank
@@ Property / cites work @@
+Approximating the Minimum Spanning Tree Weight in Sublinear Time
+Normal rank
@@ Property / cites work @@
+Q4471376
@@ Property / cites work: Q4471376 / rank @@
+Normal rank
@@ Property / cites work @@
+Estimating the weight of metric minimum spanning trees in sublinear-time
+Normal rank
@@ Property / cites work @@
+Q4763326
@@ Property / cites work: Q4763326 / rank @@
+Normal rank
@@ Property / cites work @@
+The pairing heap: A new form of self-adjusting heap
+Normal rank
@@ Property / cites work @@
+Algorithms - ESA 2003
@@ Property / cites work: Algorithms - ESA 2003 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4023519
@@ Property / cites work: Q4023519 / rank @@
+Normal rank
@@ Property / cites work @@
+Approximation algorithms for metric facility location and             <i>k</i>             -Median problems using the primal-dual schema and Lagrangian relaxation
+Normal rank
@@ Property / cites work @@
+Q3149647
@@ Property / cites work: Q3149647 / rank @@
+Normal rank