Ronald L. Graham

Orcid: 0000-0003-3081-9351

  • University of California, San Diego, USA

According to our database1, Ronald L. Graham authored at least 178 papers between 1967 and 2022.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of one.


ACM Fellow

ACM Fellow 1999, "For seminal contributions to the analysis of algorithms, in particular the worst-case analysis of heuristics, the theory of scheduling, and computational geometry.".



In proceedings 
PhD thesis 


Online presence:



Guessing about Guessing: Practical Strategies for Card Guessing with Feedback.
Am. Math. Mon., 2022

Card guessing with partial feedback.
Comb. Probab. Comput., 2022

Permanental generating functions and sequential importance sampling.
Adv. Appl. Math., 2021

Efficient Packings of Unit Squares in a Large Square.
Discret. Comput. Geom., 2020

Three-dimensional Floorplan Representations by Using Corner Links and Partial Order.
ACM Trans. Design Autom. Electr. Syst., 2019

Maximally Nontransitive Dice.
Am. Math. Mon., 2018

Sum sequences modulo <i>n</i>.
J. Comb. Theory A, 2018

Tree Structures and Algorithms for Physical Design.
Proceedings of the 2018 International Symposium on Physical Design, 2018

The drop polynomial of a weighted digraph.
J. Comb. Theory B, 2017

Parking distributions on trees.
Eur. J. Comb., 2017

Inserting Plus Signs and Adding.
Am. Math. Mon., 2016

The Mathematics of the Flip and Horseshoe Shuffles.
Am. Math. Mon., 2016

Anarchy Is Free in Network Creation.
ACM Trans. Algorithms, 2016

Worst-case analysis of the LPT algorithm for single processor scheduling with time restrictions.
OR Spectr., 2016

3D floorplan representations: Corner links and partial order.
Proceedings of the 2016 IEEE International 3D Systems Integration Conference, 2016

Egyptian Fractions with Each Denominator Having Three Distinct Prime Divisors.
Integers, 2015

Partition and sum is fast.
CoRR, 2015

Edge flipping in the complete graph.
Adv. Appl. Math., 2015

Single-processor scheduling with time restrictions.
J. Sched., 2014

De Bruijn Sequences with Varying Combs.
Integers, 2014

Unseparated pairs and fixed points in random permutations.
Adv. Appl. Math., 2014

Subdivision Using Angle Bisectors Is Dense in the Space of Triangles.
Am. Math. Mon., 2013

Inversion-descent polynomials for restricted permutations.
J. Comb. Theory A, 2013

Constructing Points through Folding and Intersection.
Int. J. Comput. Geom. Appl., 2013

Ramsey Theory in the Work of Paul Erdős.
Proceedings of the Mathematics of Paul Erdős II, 2013

A note on marking lines in [k] n - In honor of Rick Wilson's 65th birthday.
Des. Codes Cryptogr., 2012

Edge flipping in graphs.
Adv. Appl. Math., 2012

Character design and stamp algorithms for Character Projection Electron-Beam Lithography.
Proceedings of the 17th Asia and South Pacific Design Automation Conference, 2012

Bus Matrix Synthesis Based on Steiner Graphs for Power Efficient System-on-Chip Communications.
IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2011

Hypercube orientations with only two in-degrees.
J. Comb. Theory A, 2011

Some Ramsey-type results for the n-cube.
J. Comb. Theory A, 2010

Finding Patterns Avoiding Many Monochromatic Constellations.
Exp. Math., 2010

Descent polynomials for permutations with bounded drop size.
Eur. J. Comb., 2010

How to play the Majority game with a liar.
Discret. Math., 2010

Irreducible Apollonian Configurations and Packings.
Discret. Comput. Geom., 2010

Tiling Polygons with Lattice Triangles.
Discret. Comput. Geom., 2010

Physical synthesis of bus matrix for high bandwidth low power on-chip communications.
Proceedings of the 2010 International Symposium on Physical Design, 2010

Approximately optimal trees for group key management with batch updates.
Theor. Comput. Sci., 2009

Packing equal squares into a large square.
J. Comb. Theory A, 2009

Minimum perimeter rectangles that enclose congruent non-overlapping circles.
Discret. Math., 2009

Bubblesort and Juggling Sequences.
Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Primitive Juggling Sequences.
Am. Math. Mon., 2008

Erratum: Quasi-random graphs with given degree sequences.
Random Struct. Algorithms, 2008

Quasi-random graphs with given degree sequences.
Random Struct. Algorithms, 2008

Enumerating split-pair arrangements.
J. Comb. Theory A, 2008

Analysis of greedy approximations with nonsubmodular potential functions.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

3-D floorplanning using labeled tree and dual sequences.
Proceedings of the 2008 International Symposium on Physical Design, 2008

Optimal Tree Structures for Group Key Management with Batch Updates.
SIAM J. Discret. Math., 2007

Oblivious and Adaptive Strategies for the Majority and Plurality Problems.
Algorithmica, 2007

Approximately Optimal Trees for Group Key Management with Batch Updates.
Proceedings of the Theory and Applications of Models of Computation, 2007

How to Play the Majority Game with Liars.
Proceedings of the Algorithmic Aspects in Information and Management, 2007

On the construction of zero-deficiency parallel prefix circuits with minimum depth.
ACM Trans. Design Autom. Electr. Syst., 2006

Parallelism versus Memory Allocation in Pipelined Router Forwarding Engines.
Theory Comput. Syst., 2006

Maximizing data locality in distributed systems.
J. Comput. Syst. Sci., 2006

Apollonian Circle Packings: Geometry and Group Theory III. Higher Dimensions.
Discret. Comput. Geom., 2006

Apollonian Circle Packings: Geometry and Group Theory II. Super-Apollonian Group and Integral Packings.
Discret. Comput. Geom., 2006

Timing model reduction for hierarchical timing analysis.
Proceedings of the 2006 International Conference on Computer-Aided Design, 2006

Communication latency aware low power NoC synthesis.
Proceedings of the 43rd Design Automation Conference, 2006

Apollonian Circle Packings: Geometry and Group Theory I. The Apollonian Group.
Discret. Comput. Geom., 2005

Constructing zero-deficiency parallel prefix adder of minimum depth.
Proceedings of the 2005 Conference on Asia South Pacific Design Automation, 2005

Euclidean Ramsey Theory.
Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

Parallelism versus memory allocation in pipelined router forwarding engines.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Floorplan representations: Complexity and connections.
ACM Trans. Design Autom. Electr. Syst., 2003

Guessing Secrets with Inner Product Questions.
Internet Math., 2003

Finding Favorites
Electron. Colloquium Comput. Complex., 2003

A hierarchical three-way interconnect architecture for hexagonal processors.
Proceedings of the 5th International Workshop on System-Level Interconnect Prediction (SLIP 2003), 2003

Ramsey Properties of Families of Graphs.
J. Comb. Theory B, 2002

New bounds on a hypercube coloring problem.
Inf. Process. Lett., 2002

Sparse Quasi-Random Graphs.
Comb., 2002

Balancing the Interconnect Topology for Arrays of Processors between Cost and Power.
Proceedings of the 20th International Conference on Computer Design (ICCD 2002), 2002

Dynamic location problems with limited look-ahead .
Theor. Comput. Sci., 2001

Distance Realization Problems with Applications to Internet Tomography.
J. Comput. Syst. Sci., 2001

Guessing Secrets.
Electron. J. Comb., 2001

On Bipartite Graphs with Linear Ramsey Numbers.
Comb., 2001

Combinatorics for the East Model.
Adv. Appl. Math., 2001

New Bounds on a Hypercube Coloring Problem and Linear Codes.
Proceedings of the 2001 International Symposium on Information Technology (ITCC 2001), 2001

Revisiting floorplan representations.
Proceedings of the 2001 International Symposium on Physical Design, 2001

On graphs with linear Ramsey numbers.
J. Graph Theory, 2000

Improving Dense Packings of Equal Disks in a Square.
Electron. J. Comb., 2000

Dense packings of congruent circles in a circle.
Discret. Math., 1998

Forced Convex n -Gons in the Plane.
Discret. Comput. Geom., 1998

Combinatorial Problems Arising in Massive Data Sets (Abstract).
Proceedings of the Computing and Combinatorics, 4th Annual International Conference, 1998

Stratified random walks on the n-cube.
Random Struct. Algorithms, 1997

The Steiner ratio for the dual normed plane.
Discret. Math., 1997

Curved Hexagonal Packings of Equal Disks in a Circle.
Discret. Comput. Geom., 1997

Random walks on generating sets for finite groups.
Electron. J. Comb., 1997

On sampling with Markov chains.
Random Struct. Algorithms, 1996

Repeated Patterns of Dense Packings of Equal Disks in a Square.
Electron. J. Comb., 1996

On the Cover Polynomial of a Digraph.
J. Comb. Theory B, 1995

A tight lower bound for the Steiner ratio in Minkowski planes.
Discret. Math., 1995

Dense Packings of Equal Disks in an Equilateral Triangle: from 22 to 34 and Beyond.
Electron. J. Comb., 1995

Dense Packings of 3k(k+1)+1 Equal Disks in a Circle for k=1, 2, 3, 4 and 5.
Proceedings of the Computing and Combinatorics, First Annual International Conference, 1995

Routing Permutations on Graphs Via Matchings.
SIAM J. Discret. Math., 1994

A Note on the Binomial Drop Polynomial of a Poset.
J. Comb. Theory A, 1994

Recent trends in Euclidean Ramsey theory.
Discret. Math., 1994

Quasi-Random Combinatorial Structures (Abstract).
Proceedings of the Algorithms and Computation, 5th International Symposium, 1994

Concrete mathematics - a foundation for computer science (2. ed.).
Addison-Wesley, ISBN: 978-0-201-55802-9, 1994

Concrete Mathematics: A Foundation for Computer Science, 2nd Ed.
Addison-Wesley, ISBN: 0-201-55802-5, 1994

Lexicographic Ramsey Theory.
J. Comb. Theory A, 1993

On hypergraphs having evenly distributed subhypergraphs.
Discret. Math., 1993

Minimum Steiner Trees in Normed Planes.
Discret. Comput. Geom., 1993

Quasi-Random Subsets of Integer<sub>n</sub>.
J. Comb. Theory A, 1992

Binomial coefficient codes over GF(2).
Discret. Math., 1992

Universal cycles for combinatorial structures.
Discret. Math., 1992

Bounds for arrays of dots with distinct slopes or lengths.
Comb., 1992

Quasi-random tournaments.
J. Graph Theory, 1991

Asymptotic Analysis of a Random Walk on a Hypercube with Many Dimensions.
Random Struct. Algorithms, 1990

Quasi-Random Hypergraphs.
Random Struct. Algorithms, 1990

Iterated combinatorial density theorems.
J. Comb. Theory A, 1990

Penny-Packing and Two-Dimensional Codes.
Discret. Comput. Geom., 1990

Maximal antiramsey graphs and the strong chromatic number.
J. Graph Theory, 1989

Quasi-random graphs.
Comb., 1989

A dynamic location problem for graphs.
Comb., 1989

On the Improbability of Reaching Byzantine Agreements (Preliminary Version)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Concrete mathematics - a foundation for computer science.
Addison-Wesley, ISBN: 978-0-201-14236-5, 1989

On the Fractional Covering Number of Hypergraphs.
SIAM J. Discret. Math., 1988

Pursuit - Evasion games on graphs.
J. Graph Theory, 1988

Quantitative theorems for regular systems of equations.
J. Comb. Theory A, 1988

On induced subgraphs of the cube.
J. Comb. Theory A, 1988

Highly irregular graphs.
J. Graph Theory, 1987

Induced restricted Ramsey theorems for spaces.
J. Comb. Theory A, 1987

On subsets of abelian groups with no 3-term arithmetic progression.
J. Comb. Theory A, 1987

The Radon transform on Abelian Groups.
J. Comb. Theory A, 1987

Large minimal sets which force long arithmetic progressions.
J. Comb. Theory A, 1986

Some intersection theorems for ordered sets and graphs.
J. Comb. Theory A, 1986

On the covering radius of codes.
IEEE Trans. Inf. Theory, 1985

Classes of interval graphs under expanding length restrictions.
J. Graph Theory, 1985

Quantitative Forms of a Theorem of Hilbert.
J. Comb. Theory A, 1985

On the addressing problem for directed graphs.
Graphs Comb., 1985

Intersection Theorems for Vector Spaces.
Eur. J. Comb., 1985

On the History of the Minimum Spanning Tree Problem.
IEEE Ann. Hist. Comput., 1985

Euclidean Ramsey theorems on the <i>n</i>-sphere.
J. Graph Theory, 1983

A Canonical Partition Theorem for Equivalence Relations on Z<sup>t</sup>.
J. Comb. Theory A, 1983

Finding the Convex Hull of a Simple Polygon.
J. Algorithms, 1983

Edge-colored complete graphs with precisely colored subgraphs.
Comb., 1983

Minimal Decompositions of Hypergraphs into Mutually Isomorphic Subhypergraphs.
J. Comb. Theory A, 1982

Applications of the FKG Inequality and Its Relatives.
Proceedings of the Mathematical Programming The State of the Art, 1982

Homogeneous Collinear Sets in Partitions of Z<sup>n</sup>.
J. Comb. Theory A, 1981

Universal caterpillars.
J. Comb. Theory B, 1981

Minimal decompositions of graphs into mutually isomorphic subgraphs.
Comb., 1981

Lower bounds for constant weight codes.
IEEE Trans. Inf. Theory, 1980

Some Monotonicity Properties of Partial Orders.
SIAM J. Algebraic Discret. Methods, 1980

On Additive Bases and Harmonious Graphs.
SIAM J. Algebraic Discret. Methods, 1980

On the Structure of t-Designs.
SIAM J. Algebraic Discret. Methods, 1980

On Unimodality for Linear Extensions of Partial Orders.
SIAM J. Algebraic Discret. Methods, 1980

A Note on the Intersection Properties of Subsets of Integers.
J. Comb. Theory A, 1980

On Partitions of E<sup>n</sup>.
J. Comb. Theory A, 1980

Information Bounds Are Weak in the Shortest Distance Problem.
J. ACM, 1980

On a Diophantine Equation Arising in Graph Theory.
Eur. J. Comb., 1980

Combinatorial designs related to the strong perfect graph conjecture.
Discret. Math., 1979

On subgraph number independence in trees.
J. Comb. Theory B, 1978

The Number of Baxter Permutations.
J. Comb. Theory A, 1978

On graphs which contain all small trees.
J. Comb. Theory B, 1978

Performance Guarantees for Scheduling Algorithms.
Oper. Res., 1978

Addition chains with multiplicative cost.
Discret. Math., 1978

On the distance matrix of a directed graph.
J. Graph Theory, 1977

Resource Constrained Scheduling as Generalized Bin Packing.
J. Comb. Theory A, 1976

On the distance matrix of a tree.
Discret. Math., 1976

Some NP-Complete Geometric Problems
Proceedings of the 8th Annual ACM Symposium on Theory of Computing, 1976

Bounds for Multiprocessor Scheduling with Resource Constraints.
SIAM J. Comput., 1975

The Largest Small Hexagon.
J. Comb. Theory A, 1975

On Packing Squares with Equal Squares.
J. Comb. Theory A, 1975

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms.
SIAM J. Comput., 1974

Problem #7.
SIGSAM Bull., 1974

Performance Bounds on the Splitting Algorithm for Binary Testing.
Acta Informatica, 1974

Covering the Positive Integers by Disjoint Sets of the Form {[n alpha + beta]: n = 1, 2, ...}.
J. Comb. Theory A, 1973

Euclidean Ramsey Theorems I.
J. Comb. Theory A, 1973

Bounds on Scheduling with Limited Resources.
Proceedings of the Fourth Symposium on Operating System Principles, 1973

An Efficient Algorithm for Determining the Convex Hull of a Finite Planar Set.
Inf. Process. Lett., 1972

Complements and transitive closures.
Discret. Math., 1972

Optimal Scheduling for Two-Processor Systems.
Acta Informatica, 1972

Worst-Case Analysis of Memory Allocation Algorithms
Proceedings of the 4th Annual ACM Symposium on Theory of Computing, 1972

Bounds on multiprocessing anomalies and related packing algorithms.
Proceedings of the American Federation of Information Processing Societies: AFIPS Conference Proceedings: 1972 Spring Joint Computer Conference, 1972

Universal Single Transition Time Asynchronous State Assignments.
IEEE Trans. Computers, 1969

Bounds on Multiprocessing Timing Anomalies.
SIAM Journal of Applied Mathematics, 1969

An Upper Bound on Minimum Distance for a k-ary Code
Inf. Control., July, 1968

On Finite 0-Simple Semigroups and Graph Theory.
Math. Syst. Theory, 1968

On n-Valued Functionally Complete Truth Functions.
J. Symb. Log., 1967