Trans-dichotomous algorithms for minimum spanning trees and shortest paths

The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic lim...

Full description

Saved in:
Bibliographic Details
Main Authors: Fredman, M.L., Willard, D.E.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Arithmetic
Computational modeling
Concurrent computing
Costs
Data structures
Inference algorithms
Performance evaluation
Tree data structures
Tree graphs
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The fusion tree method is extended to develop a linear-time algorithm for the minimum spanning tree problem and an O(m+n log n/log log n) implementation of Dijkstra's shortest-path algorithm for a graph with n vertices and m edges. The shortest-path algorithm surpasses information-theoretic limitations. The extension of the fusion tree method involves the development of a new data structure, the atomic heap. The atomic heap accommodates heap (priority queue) operations in constant amortized time under suitable polylog restrictions on the heap size. The linear-time minimum spanning tree algorithm results from a direct application of the atomic heap. To obtain the shortest path algorithm, the atomic heap is used as a building block to construct a new data structure, the AF-heap, which has no size restrictions and surpasses information theoretic limitations. The AF-heap belongs to the Fibonacci heap family.< >
DOI:10.1109/FSCS.1990.89594