Michael L. Fredman

According to our database1, Michael L. Fredman
  • authored at least 56 papers between 1975 and 2016.
  • has a "Dijkstra number"2 of three.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

On csauthors.net:

Bibliography

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

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
Hash Functions for Priority Queues
Information and Control, December, 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


  Loading...