Dan E. Willard

SODA Conference 1992 Conference Paper

Applications of the Fusion Tree Method to Computational Geometry and Searching

• Dan E. Willard

STOC Conference 1990 Conference Paper

BLASTING through the Information Theoretic Barrier with FUSION TREES

• Michael L. Fredman
• Dan E. Willard

FOCS Conference 1990 Conference Paper

Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths

• Michael L. Fredman
• Dan E. Willard

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. >

STOC Conference 1984 Conference Paper

Log-Logarithmic Protocols for Resolving Ethernet and Semaphore Conflicts (Preliminary Report)

• Dan E. Willard

STOC Conference 1982 Conference Paper

Maintaining Dense Sequential Files in a Dynamic Environment (Extended Abstract)

• Dan E. Willard