By Professor Catherine Greenhill

Journal articles

Greenhill C; McKay BD; Wang X, 2006, 'Asymptotic enumeration of sparse 0-1 matrices with irregular row and column sums', Journal of Combinatorial Theory Series A, 113, pp. 291 - 324, http://dx.doi.org/10.1016/j.jcta.2005.03.005

Gerke S; Greenhill C; Wormald N, 2006, 'The generalized acyclic edge chromatic number of random regular graphs', Journal of Graph Theory, 53, pp. 101 - 125, http://dx.doi.org/10.1002/jgt.20167

Brinkmann G; Greenberg S; Greenhill C; McKay BD; Thomas R; Wollan P, 2005, 'Generation of simple quadrangulations of the sphere', Discrete Mathematics, 305, pp. 33 - 54, http://dx.doi.org/10.1016/j.disc.2005.10.005

Greenhill C; Pikhurko O, 2005, 'Bounds on the generalised acyclic chromatic numbers of bounded degree graphs', Graphs and Combinatorics, 21, pp. 407 - 419, http://dx.doi.org/10.1007/s00373-005-0635-y

Cooper C; Dyer M; Greenhill C, 2005, 'Sampling regular graphs and a peer-to-peer network', Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, pp. 980 - 988

Greenhill C; Ruciński A; Wormald NC, 2004, 'Random hypergraph processes with degree restrictions', Graphs and Combinatorics, 20, pp. 319 - 332, http://dx.doi.org/10.1007/s00373-004-0571-2

Dyer M; Greenhill C, 2004, 'Erratum: The complexity of counting graph homomorphisms (Random Structures Algorithms (2000) 17 (260-289))', Random Structures and Algorithms, 25, pp. 346 - 352, http://dx.doi.org/10.1002/rsa.20036

Greenhill C; Kim JH; Wormald NC, 2004, 'Hamiltonian decompositions of random bipartite regular graphs', Journal of Combinatorial Theory Series B, 90, pp. 195 - 222, http://dx.doi.org/10.1016/j.jctb.2003.07.001

Dyer M; Goldberg LA; Greenhill C; Jerrum M, 2003, 'The relative complexity of approximate counting problems', Algorithmica New York, 38, pp. 471 - 500, http://dx.doi.org/10.1007/s00453-003-1073-y

Greenhill C; Ruciski A; Wormald N, 2003, 'Connectedness of the Degree Bounded Star Process', Combinatorics, Probability and Computing, 12, pp. 269 - 283, http://dx.doi.org/10.1017/S0963548302005357

Greenhill C; Janson S; Kim JH; Wormald NC, 2002, 'Permutation pseudographs and contiguity', Combinatorics Probability and Computing, 11, pp. 273 - 298, http://dx.doi.org/10.1017/S0963548301005065

Dyer M; Goldberg LA; Greenhill C; Istrate G; Jerrum M, 2002, 'Convergence of the iterated prisoner's dilemma game', Combinatorics Probability and Computing, 11, pp. 135 - 147, http://dx.doi.org/10.1017/S096354830100503X

Dyer M; Greenhill C; Molloy M, 2002, 'Very Rapid Mixing of the Glauber Dynamics for Proper Colorings on Bounded-Degree Graphs', Random Structures and Algorithms, 20, pp. 98 - 114, http://dx.doi.org/10.1002/rsa.10020

Dyer M; Greenhill C, 2000, 'Polynomial-time counting and sampling of two-rowed contingency tables', Theoretical Computer Science, 246, pp. 265 - 278, http://dx.doi.org/10.1016/S0304-3975(99)00136-X

Dyer M; Leslie Goldberg A; Greenhill C; Jerrum M; Mitzenmacheru M, 2000, 'An extension of path coupling and its application to the glauber dynamics for graph colorings', SIAM Journal on Computing, 30, pp. 1962 - 1975, http://dx.doi.org/10.1137/s0097539700372708

Dyer M; Greenhill C, 2000, 'Complexity of counting graph homomorphisms', Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, pp. 246 - 255

Dyer M; Goldberg LA; Greenhill C; Jerrum M; Mitzenmacher M, 2000, 'Extension of path coupling and its application to the Glauber dynamics for graph colourings', Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, pp. 616 - 624

Dyer M; Greenhill C, 2000, 'On Markov Chains for Independent Sets', Journal of Algorithms, 35, pp. 17 - 49, http://dx.doi.org/10.1006/jagm.1999.1071

Greenhill C, 2000, 'The complexity of counting colourings and independent sets in sparse graphs and hypergraphs', Computational Complexity, 9, pp. 52 - 72, http://dx.doi.org/10.1007/PL00001601

Dyer M; Greenhill C, 2000, 'The complexity of counting graph homomorphisms', Random Structures and Algorithms, 17, pp. 260 - 289, http://dx.doi.org/10.1002/1098-2418(200010/12)17:3/4<260::aid-rsa5>3.0.co;2-w

Greenhill C, 2000, 'An Algorithm for Recognising the Exterior Square of a Multiset', LMS Journal of Computation and Mathematics, 3, pp. 96 - 116, http://dx.doi.org/10.1112/s1461157000000231

Greenhill C, 1999, 'An algorithm for recognising the exterior square of a matrix', Linear and Multilinear Algebra, 46, pp. 213 - 244, http://dx.doi.org/10.1080/03081089908818615

Bubley R; Dyer M; Greenhill C; Jerrum M, 1999, 'On approximately counting colorings of small degree graphs', SIAM Journal on Computing, 29, pp. 387 - 400, http://dx.doi.org/10.1137/S0097539798338175

Dyer M; Greenhill C, 1998, 'A more rapidly mixing Markov chain for graph colorings', Random Structures and Algorithms, 13, pp. 285 - 317, http://dx.doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4<285::aid-rsa6>3.0.co;2-r

Dyer M; Greenhill C, 1998, 'A genuinely polynomial-time algorithm for sampling two-rowed contingency tables', , pp. 339 - 350, http://dx.doi.org/10.1007/BFb0055065

Greenhill CS, 1995, 'Theoretical and Experimental Comparison of Efficiency of Finite Field Extensions', Journal of Symbolic Computation, 20, pp. 419 - 429, http://dx.doi.org/10.1006/jsco.1995.1057

Greenhill CS; Street AP, 1995, 'Smallest defining sets of some small t-designs and relations to the Petersen graph', Utilitas Mathematica, 48, pp. 5 - 31

Greenhill CS, 1993, 'An algorithm for finding smallest defining sets of t-designs', Journal of Combinatorial Mathematics and Combinatorial Computing, 14, pp. 39 - 60

Conference Papers

Cooper C; Dyer M; Greenhill C, 2021, 'A Triangle Process on Regular Graphs', in Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, pp. 310 - 323, http://dx.doi.org/10.1007/978-3-030-79987-8_22

Greenhill C; Mans B; Pourmiri A, 2020, 'Balanced allocation on dynamic hypergraphs', in Byrka J (ed.), Leibniz International Proceedings in Informatics Lipics, SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS, ELECTR NETWORK, presented at 2020 International Conference on Approximation Algorithms for Combinatorial Optimization Problems/ International Conference on Randomization and Computation-APPROX/RANDOM, ELECTR NETWORK, 17 August 2020 - 19 August 2020, http://dx.doi.org/10.4230/LIPIcs.APPROX/RANDOM.2020.11

Dyer M; Greenhill C; Müller H, 2019, 'Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth', in Sau I; Thilikos DM (ed.), Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, Springer Nature, SPAIN, Vall de Nuria, pp. 298 - 310, presented at 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG), SPAIN, Vall de Nuria, 19 June 2019 - 21 June 2019, http://dx.doi.org/10.1007/978-3-030-30786-8_23

Greenhill C, 2015, 'The switch markov chain for sampling irregular graphs (extended abstract)', in Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, pp. 1564 - 1572, http://dx.doi.org/10.1137/1.9781611973730.103

Dyer M; Greenhill CS, 2000, 'An extension of path coupling and its application to the Glauber dynamics for graph colourings (Extended abstract)', New York-Philadelphia, pp. 616 - 624, presented at 11th Annual ACM-SIAM Symposium on Discrete Algorithms, 09 January 2000 - 11 January 2000

Dyer M; Greenhill C, 2000, 'The complexity of counting graph homomorphisms (extended abstract)', in PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SIAM, CA, SAN FRANCISCO, pp. 246 - 255, presented at 11th Annual ACM/SIAM Symposium on Discrete Algorithms, CA, SAN FRANCISCO, 09 January 2000 - 11 January 2000

Dyer M; Goldberg LA; Greenhill C; Jerrum M, 2000, 'On the relative complexity of approximate counting problems', in Lecture Notes in Computer Science Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics, pp. 108 - 119, http://dx.doi.org/10.1007/3-540-44436-x_12

Bubley R; Dyer M; Greenhill CS, 1998, 'Beating the $2\Delta$ bound for approximately counting colourings: a computer-assisted proof of rapid mixing', in The 9th Annual ACM-SIAM Symposium on Discrete Algorithms, New York-Philidelphia, pp. 355 - 363, 25 January 1998 - 27 January 1998

Preprints

Greenhill C; Isaev M; Lewis C, 2026, Jaeger-type orientations of random regular graphs, https://arxiv.org/abs/2604.22219v1

Greenhill C; Makai T, 2026, Enumeration of dihypergraphs with specified degrees and edge types, http://dx.doi.org/10.48550/arxiv.2408.12874

Greenhill C; Hasheminezhad M; Iliffe I; McKay BD, 2026, Asymptotic enumeration of constrained bipartite, directed and oriented graphs by degree sequence, http://dx.doi.org/10.48550/arxiv.2601.04822

Cooper C; Dyer M; Greenhill C, 2019, Triangle-creation processes on cubic graphs

Cooper C; Dyer M; Greenhill C, 2012, Corrigendum: Sampling regular graphs and a peer-to-peer network, https://arxiv.org/abs/1203.6111v1

Back to profile page