By Professor Catherine Greenhill

Journal articles

Gerke S; Greenhill CS; Wormald NC, 2006, 'The generalized acyclic edge chromatic number of random regular graphs', Journal of Graph Theory, 53, pp. 101 - 125

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 CS; Pikhurko O, 2005, 'Bounds on the generalised acyclic chronatic numbers of bounded degree graphs', Graphs and Combinatorics, 21, pp. 407 - 419

Brinkmann G; Greenberg S; Greenhill CS; McKay BD; Thomas R; Wollan P, 2005, 'Generation of simple quadrangulations of the sphere', Discrete Mathematics, 305, pp. 33 - 54

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

Greenhill CS; Dyer M, 2004, 'Corrigendum: The complexity of counting graph homomorphisms (Vol 17, pg 260, 2000)', Random Structures and Algorithms, 25, pp. 346 - 352

Greenhill CS; Rucinski A; Wormald NC, 2004, 'Random hypergraph processes with degree restrictions', Graphs and Combinatorics, 20, pp. 319 - 332

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

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

Greenhill C; Janson S; Kim J; Wormald N, 2002, 'Permutation Pseudographs and Contiguity', Combinatorics, Probability and Computing, 11, http://dx.doi.org/10.1017/S0963548301005065

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, 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 Flocchini P; Moura L (ed.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Nature, ELECTR NETWORK, pp. 310 - 323, presented at 32nd International Workshop on Combinatorial Algorithms (IWOCA), ELECTR NETWORK, 05 July 2021 - 07 July 2021, 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 Leibniz International Proceedings in Informatics, LIPIcs, http://dx.doi.org/10.4230/lipics.approx/random.2020.11

Greenhill CS, 2015, 'The switch Markov chain for sampling irregular graphs', in The 26th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM-SIAM, San Diego, CA, USA, pp. 1565 - 1572, presented at 26th annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA, 04 January 2015 - 06 January 2015, 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)', in PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, SIAM, New York-Philadelphia, pp. 616 - 624, presented at 11th Annual ACM-SIAM Symposium on Discrete Algorithms, SAN FRANCISCO, CA, 09 January 2000 - 11 January 2000, http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000085602800082&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a

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, https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000085602800035&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=891bb5ab6ba270e68a29b250adbe88d1

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

Working Papers

Greenhill C; Isaev M; Makai T; McKay BD, 2021, Degree sequences of sufficiently dense random uniform hypergraphs, http://dx.doi.org, http://arxiv.org/abs/2106.08100v2

Preprints

Delcourt M; Greenhill C; Isaev M; Lidický B; Postle L, 2023, Decomposing random regular graphs into stars, , http://arxiv.org/abs/2308.16037v1

Cooper C; Dyer M; Greenhill C, 2023, A triangle process on graphs with given degree sequence, , http://arxiv.org/abs/2301.08499v1

Greenhill C, 2022, Generating graphs randomly, , http://arxiv.org/abs/2201.04888v1

Dyer M; Greenhill C; Kleer P; Ross J; Stougie L, 2020, Sampling hypergraphs with given degrees, , http://dx.doi.org/10.48550/arxiv.2006.12021

Aldosari HS; Greenhill C, 2019, The average number of spanning hypertrees in sparse uniform hypergraphs, , http://dx.doi.org/10.48550/arxiv.1907.04993

Erdős PL; Greenhill C; Mezei TR; Miklós I; Soltész D; Soukup L, 2019, The mixing time of the switch Markov chains: a unified approach, , http://dx.doi.org/10.48550/arxiv.1903.06600

Aldosari HS; Greenhill C, 2018, Enumerating sparse uniform hypergraphs with given degree sequence and forbidden edges, , http://dx.doi.org/10.48550/arxiv.1805.04991

Altman D; Greenhill C; Isaev M; Ramadurai R, 2016, A threshold result for loose Hamiltonicity in random regular uniform hypergraphs, , http://dx.doi.org/10.48550/arxiv.1611.09423

Ayre P; Coja-Oghlan A; Greenhill C, 2015, Hypergraph coloring up to condensation, , http://dx.doi.org/10.48550/arxiv.1508.01841

Blinovsky V; Greenhill C, 2014, Asymptotic enumeration of sparse uniform linear hypergraphs with given degrees, , http://dx.doi.org/10.48550/arxiv.1409.1314

Blinovsky V; Greenhill C, 2013, Asymptotic enumeration of sparse uniform hypergraphs with given degrees, , http://dx.doi.org/10.48550/arxiv.1306.2012

Back to profile page