# Michael L. Fredman

According to our database

Collaborative distances:

^{1}, Michael L. Fredman authored at least 52 papers between 1975 and 2014.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2014

An intuitive and simple bounding argument for Quicksort.

Inf. Process. Lett., 2014

2012

Generalizing a Theorem of Wilber on Rotations in Binary Search Trees to Encompass Unordered Binary Trees.

Algorithmica, 2012

2011

On the Matter of Dynamic Optimality in an Extended Model for Tree Access Operations.

Proceedings of the Algorithms and Data Structures - 12th International Symposium, 2011

2008

Adaptive sorting: an information theoretic perspective.

Acta Inf., 2008

2005

Worst case constant time priority queue.

Journal of Systems and Software, 2005

2004

Binomial, Fibonacci, and Pairing Heaps.

Proceedings of the Handbook of Data Structures and Applications., 2004

2003

The number of tests required to search an unordered table.

Inf. Process. Lett., 2003

Adaptive Sorting and the Information Theoretic Lower Bound.

Proceedings of the STACS 2003, 20th Annual Symposium on Theoretical Aspects of Computer Science, Berlin, Germany, February 27, 2003

1999

On the Efficiency of Pairing Heaps and Related Data Structures.

J. ACM, 1999

A Priority Queue Transform.

Proceedings of the Algorithm Engineering, 1999

1998

Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums.

SIAM J. Comput., 1998

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.

Algorithmica, 1998

Information Theoretic Implications for Pairing Heaps.

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

1997

The AETG System: An Approach to Testing Based on Combinatiorial Design.

IEEE Trans. Software Eng., 1997

1996

On the Complexity of Dualization of Monotone Disjunctive Normal Forms.

J. Algorithms, 1996

Weighted Binary Trees for Concurrent Searching.

J. Algorithms, 1996

1994

Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.

J. Comput. Syst. Sci., 1994

Three Stacks.

J. Algorithms, 1994

Lower Bounds for Dynamic Algorithms.

Proceedings of the Algorithm Theory, 1994

1993

Surpassing the Information Theoretic Bound with Fusion Trees.

J. Comput. Syst. Sci., 1993

Data Structures for Traveling Salesmen.

Proceedings of the Fourth Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1993

Products of Finite State Machines with Full Coverage.

Proceedings of the Automata, Languages and Programming, 20nd International Colloquium, 1993

Optimal Bi-Weighted Binary Trees and the Complexity of Maintaining Partial Sums

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1990

BLASTING through the Information Theoretic Barrier with FUSION TREES

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

The Cell Probe Complexity of Dynamic Data Structures

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988

Three Stacks

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1987

Refined Complexity Analysis for Heap Operations.

J. Comput. Syst. Sci., 1987

Fibonacci heaps and their uses in improved network optimization algorithms.

J. ACM, 1987

1986

The Pairing Heap: A New Form of Self-Adjusting Heap.

Algorithmica, 1986

1984

Storing a Sparse Table with 0(1) Worst Case Access Time.

J. ACM, 1984

Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

1983

Hash Functions for Priority Queues

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

1982

The Complexity of Partial Match Retrieval in a Dynamic Setting.

J. Algorithms, 1982

The Complexity of Maintaining an Array and Computing Its Partial Sums.

J. ACM, 1982

Storing a Sparse Table with O(1) Worst Case Access Time

Proceedings of the 23rd Annual Symposium on Foundations of Computer Science, 1982

1981

Inherent Complexity Trade-Offs for Range Query Problems.

Theor. Comput. Sci., 1981

Observations Concerning the Complexity of a Class of On-Line Algebraic Problems.

IEEE Trans. Computers, 1981

Lower Bounds on the Complexity of Some Optimal Data Structures.

SIAM J. Comput., 1981

Query Time Versus Redundancy Trade-Offs for Range Queries.

J. Comput. Syst. Sci., 1981

The Spanning Bound as a Measure of Range Query Complexity.

J. Algorithms, 1981

A Lower Bound on the Complexity of Orthogonal Range Queries.

J. ACM, 1981

1980

The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries

Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980

1979

A Near Optimal Data Structure for a Type of Range Query Problem

Proceedings of the 11h Annual ACM Symposium on Theory of Computing, April 30, 1979

1978

Observations on the Complexity of Generating Quasi-Gray Codes.

SIAM J. Comput., 1978

On the Complexity of Computing the Measure of U[ai, bi].

Commun. ACM, 1978

1976

How Good is the Information Theory Bound in Sorting?

Theor. Comput. Sci., 1976

New Bounds on the Complexity of the Shortest Path Problem.

SIAM J. Comput., 1976

1975

A Symmetry Relationship for a Class of Partitions.

J. Comb. Theory, Ser. A, 1975

On computing the length of longest increasing subsequences.

Discrete Mathematics, 1975

Two Applications of a Probabilistic Search Technique: Sorting x + y and Building Balanced Search Trees

Proceedings of the 7th Annual ACM Symposium on Theory of Computing, 1975

On the Decision Tree Complexity of the Shortest Path Problems

Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975