The saga of minimum spanning trees
From MaRDI portal
Publication:458468
DOI10.1016/j.cosrev.2008.10.002zbMath1302.68219OpenAlexW1981755382MaRDI QIDQ458468
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2008.10.002
Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (4)
Relation-Algebraic Verification of Prim’s Minimum Spanning Tree Algorithm ⋮ A resting-state brain functional network study in MDD based on minimum spanning tree analysis and the hierarchical clustering ⋮ A note on the traveling salesman reoptimization problem under vertex insertion ⋮ An algebraic framework for minimum spanning tree problems
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A note on two problems in connexion with graphs
- On the shortest spanning subtree of a graph and the traveling salesman problem
- Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees
- On an algorithm of Zemlyachenko for subtree isomorphism
- Graph minors. XX: Wagner's conjecture
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Lower bound of the Hadwiger number of graphs by their average degree
- On the succinct representation of graphs
- An inverse-Ackermann type lower bound for online minimum spanning tree verification
- Linear verification for spanning trees
- Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
- The pairing heap: A new form of self-adjusting heap
- A sweepline algorithm for Voronoi diagrams
- Finding the \(k\) smallest spanning trees
- Preserving order in a forest in less than logarithmic time and linear space
- Lower bounds for fully dynamic connectivity problems in graphs
- Fusion trees can be implemented with \(AC^0\) instructions only
- Surpassing the information theoretic bound with fusion trees
- Trans-dichotomous algorithms for minimum spanning trees and shortest paths
- A simpler minimum spanning tree verification algorithm
- Probability theory of classical Euclidean optimization problems
- Time bounds for selection
- The minimum spanning tree problem on a planar graph
- A data structure for dynamic trees
- Efficient minimum spanning tree construction with Delaynay triangulation
- Graph Isomorphism is in SPP
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- Deterministic Dictionaries
- Applications of Path Compression on Balanced Trees
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- Undirected single-source shortest paths with positive integer weights in linear time
- Randomized fully dynamic graph algorithms with polylogarithmic time per operation
- Near-optimal fully-dynamic graph connectivity
- An optimal minimum spanning tree algorithm
- Fast Algorithms for Finding Nearest Common Ancestors
- An extremal function for contractions of graphs
- Graph minor theory
- Linear-Time Ranking of Permutations
- An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
- Deterministic sorting in O ( n log log n ) time and linear space
- Estimating the weight of metric minimum spanning trees in sublinear-time
- Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
- Multi-Terminal Network Flows
- An Algorithm for Finding K Minimum Spanning Trees
- Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
- Efficiency of a Good But Not Linear Set Union Algorithm
- Finding Minimum Spanning Trees
- A data structure for manipulating priority queues
- The Rectilinear Steiner Tree Problem is $NP$-Complete
- The Complexity of Computing Steiner Minimal Trees
- Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
- A randomized linear-time algorithm to find minimum spanning trees
- Sparsification—a technique for speeding up dynamic graph algorithms
- Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
- The soft heap
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Floats, Integers, and Single Source Shortest Paths
- A New Approximation Algorithm for the Steiner Tree Problem with Performance Ratio 5/3
- Maintaining minimum spanning trees in dynamic graphs
- Purely Functional Data Structures
- On the History of the Minimum Spanning Tree Problem
- Fibonacci heaps and their uses in improved network optimization algorithms
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Sur la liaison et la division des points d'un ensemble fini
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Algorithms - ESA 2003
- Quicksort
- Integer priority queues with decrease key in constant time and the single source shortest paths problem
- Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
- Vojtěch Jarník's work in combinatorial optimization
This page was built for publication: The saga of minimum spanning trees
