Michael L. Fredman
According to our database1, Michael L. Fredman authored at least 52 papers between 1975 and 2014.
Legend:Book In proceedings Article PhD thesis Other
An intuitive and simple bounding argument for Quicksort.
Inf. Process. Lett., 2014
Generalizing a Theorem of Wilber on Rotations in Binary Search Trees to Encompass Unordered Binary Trees.
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
Adaptive sorting: an information theoretic perspective.
Acta Inf., 2008
Worst case constant time priority queue.
Journal of Systems and Software, 2005
Binomial, Fibonacci, and Pairing Heaps.
Proceedings of the Handbook of Data Structures and Applications., 2004
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
On the Efficiency of Pairing Heaps and Related Data Structures.
J. ACM, 1999
A Priority Queue Transform.
Proceedings of the Algorithm Engineering, 1999
Optimal Biweighted Binary Trees and the Complexity of Maintaining Partial Sums.
SIAM J. Comput., 1998
Lower Bounds for Fully Dynamic Connectivity Problems in Graphs.
Information Theoretic Implications for Pairing Heaps.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
The AETG System: An Approach to Testing Based on Combinatiorial Design.
IEEE Trans. Software Eng., 1997
On the Complexity of Dualization of Monotone Disjunctive Normal Forms.
J. Algorithms, 1996
Weighted Binary Trees for Concurrent Searching.
J. Algorithms, 1996
Trans-Dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths.
J. Comput. Syst. Sci., 1994
J. Algorithms, 1994
Lower Bounds for Dynamic Algorithms.
Proceedings of the Algorithm Theory, 1994
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
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
The Cell Probe Complexity of Dynamic Data Structures
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988
Refined Complexity Analysis for Heap Operations.
J. Comput. Syst. Sci., 1987
Fibonacci heaps and their uses in improved network optimization algorithms.
J. ACM, 1987
The Pairing Heap: A New Form of Self-Adjusting Heap.
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
Hash Functions for Priority Queues
Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983
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
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
The Inherent Complexity of Dynamic Data Structures which Accommodate Range Queries
Proceedings of the 21st Annual Symposium on Foundations of Computer Science, 1980
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
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
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
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