The saga of minimum spanning trees

DOI10.1016/J.COSREV.2008.10.002zbMATH Open1302.68219OpenAlexW1981755382MaRDI QIDQ458468FDOQ458468

Authors: Martin Mareš 

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

Recommendations

• Minimum Diameter Spanning Trees and Related Problems
• Minimum spanning trees
• Minimum spanning hypertrees
• Minimum spanning trees in \(d\) dimensions
• scientific article; zbMATH DE number 1436136
• On the History of the Minimum Spanning Tree Problem
• On the minimum diameter spanning tree problem

zbMATH Keywords

minimum spanning trees

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to computer science (68-02) Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Cites Work

• Title not available (Why is that?)
• Quicksort
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A note on two problems in connexion with graphs
• Introduction to algorithms
• Sur la liaison et la division des points d'un ensemble fini
• Probability theory of classical Euclidean optimization problems
• Fibonacci heaps and their uses in improved network optimization algorithms
• Title not available (Why is that?)
• Graph minors. XX: Wagner's conjecture
• Preserving order in a forest in less than logarithmic time and linear space
• Trans-dichotomous algorithms for minimum spanning trees and shortest paths
• A data structure for dynamic trees
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• An extremal function for contractions of graphs
• Title not available (Why is that?)
• Efficiency of a Good But Not Linear Set Union Algorithm
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Lower bound of the Hadwiger number of graphs by their average degree
• Applications of Path Compression on Balanced Trees
• Title not available (Why is that?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A sweepline algorithm for Voronoi diagrams
• Graph minor theory
• Title not available (Why is that?)
• On the succinct representation of graphs
• Title not available (Why is that?)
• Linear verification for spanning trees
• Lower bounds for fully dynamic connectivity problems in graphs
• A simpler minimum spanning tree verification algorithm
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Verification and Sensitivity Analysis of Minimum Spanning Trees in Linear Time
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• Surpassing the information theoretic bound with fusion trees
• Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning trees
• On an algorithm of Zemlyachenko for subtree isomorphism
• Fast Algorithms for Finding Nearest Common Ancestors
• Deterministic sorting in O ( n log log n ) time and linear space
• Multi-Terminal Network Flows
• The Complexity of Computing Steiner Minimal Trees
• A randomized linear-time algorithm to find minimum spanning trees
• Title not available (Why is that?)
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• Fusion trees can be implemented with \(AC^0\) instructions only
• Time bounds for selection
• Sparsification—a technique for speeding up dynamic graph algorithms
• Graph Isomorphism is in SPP
• Finding the \(k\) smallest spanning trees
• An Algorithm for Finding K Minimum Spanning Trees
• 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
• Title not available (Why is that?)
• Deterministic dictionaries
• Undirected single-source shortest paths with positive integer weights in linear time
• An optimal minimum spanning tree algorithm
• On the History of the Minimum Spanning Tree Problem
• Maintaining minimum spanning trees in dynamic graphs
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Title not available (Why is that?)
• A data structure for manipulating priority queues
• Approximating the Minimum Spanning Tree Weight in Sublinear Time
• Title not available (Why is that?)
• Integer priority queues with decrease key in constant time and the single source shortest paths problem
• Finding Minimum Spanning Trees
• Title not available (Why is that?)
• The pairing heap: A new form of self-adjusting heap
• The minimum spanning tree problem on a planar graph
• Efficient minimum spanning tree construction with Delaynay triangulation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Randomized fully dynamic graph algorithms with polylogarithmic time per operation
• Near-optimal fully-dynamic graph connectivity
• Two linear time algorithms for MST on minor closed graph classes.
• Linear-Time Ranking of Permutations
• An Õ(mn) Gomory-Hu tree construction algorithm for unweighted graphs
• Estimating the weight of metric minimum spanning trees in sublinear-time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The soft heap
• Title not available (Why is that?)
• Purely Functional Data Structures
• Title not available (Why is that?)
• A practical minimum spanning tree algorithm using the cycle property
• 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
• An inverse-Ackermann type lower bound for online minimum spanning tree verification

Cited In (9)

• THE MINIMUM SPANNING TREE PROBLEM: Jarník's solution in historical and present context
• Randomized minimum spanning tree algorithms using exponentially fewer random bits
• Title not available (Why is that?)
• Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time
• 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
• An algebraic framework for minimum spanning tree problems
• A note on the traveling salesman reoptimization problem under vertex insertion
• On the History of the Minimum Spanning Tree Problem

Uses Software

• Haskell
• Quicksort
• Find

This page was built for publication: The saga of minimum spanning trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q458468)