According to our database
1,
Michael L. Fredman
authored at least 51 papers
between 1972 and 2016.
Collaborative distances:
2016
Comments on Dumitrescu's "A Selectable Sloppy Heap".
CoRR, 2016
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 Informatica, 2008
2005
Worst case constant time priority queue.
J. Syst. Softw., 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
Products of Finite State Machines with Full Coverage.
Theor. Comput. Sci., 1996
On the Complexity of Dualization of Monotone Disjunctive Normal Forms.
J. Algorithms, 1996
Weighted Binary Trees for Concurrent Searching.
J. Algorithms, 1996
1995
Data Structures for Traveling Salesmen.
J. Algorithms, 1995
1994
Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.
J. Comput. Syst. Sci., 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
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
1989
The Cell Probe Complexity of Dynamic Data Structures
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
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
Hash Functions for Priority Queues
Inf. Control., December, 1984
Storing a Sparse Table with 0(1) Worst Case Access Time.
J. ACM, 1984
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.
Discret. Math., 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
1972
Growth properties of a class of recursively defined functions.
PhD thesis, 1972