Ronald L. Graham

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

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

Awards

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Sum sequences modulo n.
J. Comb. Theory, Ser. A, 2018

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

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

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

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

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

2013
Subdivision Using Angle Bisectors Is Dense in the Space of Triangles.
The American Mathematical Monthly, 2013

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

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

Anarchy Is Free in Network Creation.
Proceedings of the Algorithms and Models for the Web Graph - 10th International Workshop, 2013

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

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

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

2011
Bus Matrix Synthesis Based on Steiner Graphs for Power Efficient System-on-Chip Communications.
IEEE Trans. on CAD of Integrated Circuits and Systems, 2011

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

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

Finding Patterns Avoiding Many Monochromatic Constellations.
Experimental Mathematics, 2010

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

How to play the Majority game with a liar.
Discrete Mathematics, 2010

Irreducible Apollonian Configurations and Packings.
Discrete & Computational Geometry, 2010

Tiling Polygons with Lattice Triangles.
Discrete & Computational Geometry, 2010

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

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

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

Minimum perimeter rectangles that enclose congruent non-overlapping circles.
Discrete Mathematics, 2009

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

2008
Primitive Juggling Sequences.
The American Mathematical Monthly, 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, Ser. 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

2007
Optimal Tree Structures for Group Key Management with Batch Updates.
SIAM J. Discrete Math., 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

2006
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.
Discrete & Computational Geometry, 2006

Apollonian Circle Packings: Geometry and Group Theory II. Super-Apollonian Group and Integral Packings.
Discrete & Computational Geometry, 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

2005
Apollonian Circle Packings: Geometry and Group Theory I. The Apollonian Group.
Discrete & Computational Geometry, 2005

Oblivious and Adaptive Strategies for the Majority and Plurality Problems.
Proceedings of the Computing and Combinatorics, 11th Annual International Conference, 2005

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

2004
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

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

Finding Favorites
Electronic Colloquium on Computational Complexity (ECCC), 2003

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

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

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

Sparse Quasi-Random Graphs.
Combinatorica, 2002

Guessing secrets with inner product questions.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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

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

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

On Bipartite Graphs with Linear Ramsey Numbers.
Combinatorica, 2001

Guessing secrets.
Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 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

2000
On graphs with linear Ramsey numbers.
Journal of Graph Theory, 2000

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

1998
Dense packings of congruent circles in a circle.
Discrete Mathematics, 1998

Forced Convex n -Gons in the Plane.
Discrete & Computational Geometry, 1998

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

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

The Steiner ratio for the dual normed plane.
Discrete Mathematics, 1997

Curved Hexagonal Packings of Equal Disks in a Circle.
Discrete & Computational Geometry, 1997

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

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

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

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

A tight lower bound for the Steiner ratio in Minkowski planes.
Discrete Mathematics, 1995

Dense Packings of Equal Disks in an Equilateral Triangle: from 22 to 34 and Beyond.
Electr. 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

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

Recent trends in Euclidean Ramsey theory.
Discrete Mathematics, 1994

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

The Tight Lower Bound for the Steiner Ratio in Minkowski Planes.
Proceedings of the Tenth Annual Symposium on Computational Geometry, 1994

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

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

On hypergraphs having evenly distributed subhypergraphs.
Discrete Mathematics, 1993

Minimum Steiner Trees in Normed Planes.
Discrete & Computational Geometry, 1993

Routing permutations on graphs via matchings.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

1992
Quasi-Random Subsets of Integern.
J. Comb. Theory, Ser. A, 1992

Binomial coefficient codes over GF(2).
Discrete Mathematics, 1992

Universal cycles for combinatorial structures.
Discrete Mathematics, 1992

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

1991
Quasi-random tournaments.
Journal of Graph Theory, 1991

1990
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, Ser. A, 1990

Penny-Packing and Two-Dimensional Codes.
Discrete & Computational Geometry, 1990

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

Quasi-random graphs.
Combinatorica, 1989

A dynamic location problem for graphs.
Combinatorica, 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

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

Pursuit - Evasion games on graphs.
Journal of Graph Theory, 1988

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

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

1987
Highly irregular graphs.
Journal of Graph Theory, 1987

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

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

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

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

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

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

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

Arrangements in Unitary and Orthogonal Geometry over Finite Fields.
J. Comb. Theory, Ser. A, 1985

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

On the addressing problem for directed graphs.
Graphs and Combinatorics, 1985

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

On the History of the Minimum Spanning Tree Problem.
IEEE Annals of the History of Computing, 1985

1983
Euclidean Ramsey theorems on the n-sphere.
Journal of Graph Theory, 1983

A Canonical Partition Theorem for Equivalence Relations on Zt.
J. Comb. Theory, Ser. A, 1983

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

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

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

1981
Homogeneous Collinear Sets in Partitions of Zn.
J. Comb. Theory, Ser. A, 1981

Universal caterpillars.
J. Comb. Theory, Ser. B, 1981

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

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

Some Monotonicity Properties of Partial Orders.
SIAM J. Matrix Analysis Applications, 1980

On Additive Bases and Harmonious Graphs.
SIAM J. Matrix Analysis Applications, 1980

On the Structure of t-Designs.
SIAM J. Matrix Analysis Applications, 1980

On Unimodality for Linear Extensions of Partial Orders.
SIAM J. Matrix Analysis Applications, 1980

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

On Partitions of En.
J. Comb. Theory, Ser. 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

1979
Combinatorial designs related to the strong perfect graph conjecture.
Discrete Mathematics, 1979

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

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

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

Performance Guarantees for Scheduling Algorithms.
Operations Research, 1978

Addition chains with multiplicative cost.
Discrete Mathematics, 1978

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

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

On the distance matrix of a tree.
Discrete Mathematics, 1976

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

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

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

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

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

Problem #7.
ACM SIGSAM Bulletin, 1974

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

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

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

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

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

Complements and transitive closures.
Discrete Mathematics, 1972

Optimal Scheduling for Two-Processor Systems.
Acta Inf., 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

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

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

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

On Finite 0-Simple Semigroups and Graph Theory.
Mathematical Systems Theory, 1968

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


  Loading...