Michael L. Fredman

According to our database, Michael L. Fredman authored at least 51 papers between 1972 and 2016.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2016

Comments on Dumitrescu's "A Selectable Sloppy Heap".

Michael L. Fredman

CoRR, 2016

2014

An intuitive and simple bounding argument for Quicksort.

Michael L. Fredman

Inf. Process. Lett., 2014

2012

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

Michael L. Fredman

Algorithmica, 2012

2011

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

Michael L. Fredman

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

2008

Adaptive sorting: an information theoretic perspective.

Amr Elmasry, Michael L. Fredman

Acta Informatica, 2008

2005

Worst case constant time priority queue.

Andrej Brodnik, Svante Carlsson, Michael L. Fredman, Johan Karlsson, J. Ian Munro

J. Syst. Softw., 2005

2004

Binomial, Fibonacci, and Pairing Heaps.

Michael L. Fredman

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

2003

The number of tests required to search an unordered table.

Michael L. Fredman

Inf. Process. Lett., 2003

Adaptive Sorting and the Information Theoretic Lower Bound.

Amr Elmasry, Michael L. Fredman

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.

Michael L. Fredman

J. ACM, 1999

A Priority Queue Transform.

Michael L. Fredman

Proceedings of the Algorithm Engineering, 1999

1998

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

Haripriyan Hampapuram, Michael L. Fredman

SIAM J. Comput., 1998

Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.

Monika Rauch Henzinger, Michael L. Fredman

Algorithmica, 1998

Information Theoretic Implications for Pairing Heaps.

Michael L. Fredman

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.

David M. Cohen, Siddhartha R. Dalal, Michael L. Fredman, Gardner C. Patton

IEEE Trans. Software Eng., 1997

1996

Products of Finite State Machines with Full Coverage.

David M. Cohen, Michael L. Fredman

Theor. Comput. Sci., 1996

On the Complexity of Dualization of Monotone Disjunctive Normal Forms.

Michael L. Fredman, Leonid Khachiyan

J. Algorithms, 1996

Weighted Binary Trees for Concurrent Searching.

David M. Cohen, Michael L. Fredman

J. Algorithms, 1996

1995

Data Structures for Traveling Salesmen.

Michael L. Fredman, David S. Johnson, Lyle A. McGeoch, G. Ostheimer

J. Algorithms, 1995

1994

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

Michael L. Fredman, Dan E. Willard

J. Comput. Syst. Sci., 1994

Three Stacks.

Michael L. Fredman, Deborah L. Goldsmith

J. Algorithms, 1994

Lower Bounds for Dynamic Algorithms.

Michael L. Fredman

Proceedings of the Algorithm Theory, 1994

1993

Surpassing the Information Theoretic Bound with Fusion Trees.

Michael L. Fredman, Dan E. Willard

J. Comput. Syst. Sci., 1993

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

Haripriyan Hampapuram, Michael L. Fredman

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

1990

BLASTING through the Information Theoretic Barrier with FUSION TREES

Michael L. Fredman, Dan E. Willard

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

1989

The Cell Probe Complexity of Dynamic Data Structures

Michael L. Fredman, Michael E. Saks

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

1987

Refined Complexity Analysis for Heap Operations.

Michael L. Fredman, Thomas H. Spencer

J. Comput. Syst. Sci., 1987

Fibonacci heaps and their uses in improved network optimization algorithms.

Michael L. Fredman, Robert Endre Tarjan

J. ACM, 1987

1986

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

Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, Robert Endre Tarjan

Algorithmica, 1986

1984

Hash Functions for Priority Queues

Miklós Ajtai, Michael L. Fredman, János Komlós

Inf. Control., December, 1984

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

Michael L. Fredman, János Komlós, Endre Szemerédi

J. ACM, 1984

1982

The Complexity of Partial Match Retrieval in a Dynamic Setting.

Michael L. Fredman, Dennis J. Volper

J. Algorithms, 1982

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

Michael L. Fredman

J. ACM, 1982

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

Michael L. Fredman, János Komlós, Endre Szemerédi

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

1981

Inherent Complexity Trade-Offs for Range Query Problems.

Walter A. Burkhard, Michael L. Fredman, Daniel J. Kleitman

Theor. Comput. Sci., 1981

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

Michael L. Fredman

IEEE Trans. Computers, 1981

Lower Bounds on the Complexity of Some Optimal Data Structures.

Michael L. Fredman

SIAM J. Comput., 1981

Query Time Versus Redundancy Trade-Offs for Range Queries.

Michael L. Fredman, Dennis J. Volper

J. Comput. Syst. Sci., 1981

The Spanning Bound as a Measure of Range Query Complexity.

Michael L. Fredman

J. Algorithms, 1981

A Lower Bound on the Complexity of Orthogonal Range Queries.

Michael L. Fredman

J. ACM, 1981

1980

The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries

Michael L. Fredman

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

Michael L. Fredman

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

1978

Observations on the Complexity of Generating Quasi-Gray Codes.

Michael L. Fredman

SIAM J. Comput., 1978

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

Michael L. Fredman, Bruce W. Weide

Commun. ACM, 1978

1976

How Good is the Information Theory Bound in Sorting?

Michael L. Fredman

Theor. Comput. Sci., 1976

New Bounds on the Complexity of the Shortest Path Problem.

Michael L. Fredman

SIAM J. Comput., 1976

1975

A Symmetry Relationship for a Class of Partitions.

Michael L. Fredman

J. Comb. Theory A, 1975

On computing the length of longest increasing subsequences.

Michael L. Fredman

Discret. Math., 1975

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

Michael L. Fredman

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

On the Decision Tree Complexity of the Shortest Path Problems

Michael L. Fredman

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

1972

Growth properties of a class of recursively defined functions.

Michael L. Fredman

PhD thesis, 1972