Priority queues with update and finding minimum spanning trees

DOI10.1016/0020-0190(75)90001-0zbMath0318.68032OpenAlexW1963503748WikidataQ56092061 ScholiaQ56092061MaRDI QIDQ1222511

Donald B. Johnson

Publication date: 1975

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(75)90001-0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Trees (05C05) Formal languages and automata (68Q45) General topics in the theory of software (68N01) Algorithms in computer science (68W99)

Related Items (19)

The d-deap\(^*\): a fast and simple cache-aligned d-ary deap ⋮ Divisor generating functions and insertion into a heap ⋮ Linear-Time Approximation for Maximum Weight Matching ⋮ Optimizing binary heaps ⋮ A novel pseudo‐polynomial approach for shortest path problems ⋮ Finding minimal spanning trees in a Euclidean coordinate space ⋮ On the relationship between the biconnectivity augmentation and traveling salesman problems ⋮ An in-depth empirical investigation of non-greedy approaches for the minimum spanning tree problem ⋮ Minimum-weight spanning tree algorithms. A survey and empirical study ⋮ A probabilistic minimum spanning tree algorithm ⋮ The efficiency of two indexed priority queue algorithms ⋮ A Dijkstra-like shortest path algorithm for certain cases of negative arc lengths ⋮ Real-time Traffic Assignment Using Engineered Customizable Contraction Hierarchies ⋮ A NOVEL LINEAR ALGORITHM FOR SHORTEST PATHS IN NETWORKS ⋮ A Survey on Priority Queues ⋮ A priority queue for the all pairs shortest path problem ⋮ A priority queue in which initialization and queue operations takeO(loglogD) time ⋮ Optimal vertex ordering of graphs ⋮ Divide-and-conquer recurrences associated with generalized heaps, optimal merge, and related structures

Cites Work

• A note on two problems in connexion with graphs
• On the shortest spanning subtree of a graph and the traveling salesman problem
• An \(0(| E|\log\log| V|)\) algorithm for finding minimum spanning trees
• Computational complexity of random access stored program machines
• Unnamed Item
• Unnamed Item

This page was built for publication: Priority queues with update and finding minimum spanning trees