Dr Kitty Meeks

Reader (School of Computing Science)

telephone: 0141 330 8469
email: Kitty.Meeks@glasgow.ac.uk

Room 406, 1 Lilybank Gardens, School of Computing Science, Sir Alwyn Williams Building, University of Glasgow

Biography

I joined the University of Glasgow in 2014, as a Lecturer in the School of Mathematics and Statistics; I moved to the School of Computing Science in 2016, where I held a Royal Society of Edinburgh Personal Research Fellowship from 2016 to 2021. My work is currently funded by an EPSRC Fellowship (2021-2026).

I gained my MMath in Mathematics and Computer Science (2009) and DPhil in Mathematics (2013) from the University of Oxford, and from 2012 to 2014 I worked as a Postdoctoral Research Assistant at Queen Mary University of London.

Research interests

My research involves developing new techniques for the design of provably correct and efficient algorithms, and applying these techniques in as many domains as possible - from Social Network Analysis to Precision Medicine. I am particularly interested in parameterised algorithms, counting complexity, and applications of graph theory.

From 2016 to 2021, I held a Personal Research Fellowship from the Royal Society of Edinburgh, to work on the project Exploiting Realistic Graph Structure. The goal of this work was to help bridge the gap between theory and practice in the design of network algorithms by developing our understanding of how structural properties of real datasets can help us to extract information from them more efficiently.

Since October 2021, I my research has been funded by an EPSRC Fellowship, Beyond One Solution in Combinatorial Optimisation. In this project I aim to develop new techniques for the design of algorithms that do more than just find a single "best" solution: we aim to find all good solutions or, failing that, to estimate the number of good solutions and sample randomly from this collection. This will involve combining techniques for the design of parameterised algorithms and approximate counting algorithms. While these abstract techniques will be very widely applicable, we have identified several target applications in the field of Precision Medicine which will be explored during the project.

For more information on my current research projects, visit my personal webpage.

Publications

List by: Type | Date

Jump to: 2025 | 2024 | 2023 | 2022 | 2021 | 2020 | 2019 | 2018 | 2017 | 2016 | 2015 | 2014 | 2013 | 2012

Number of items: 48.

2025

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 and Sylvester, John ORCID: https://orcid.org/0000-0002-6543-2934 (2025) Tangled paths: a random graph model from mallows permutations. Electronic Journal of Combinatorics, 32(2), P2.35. (doi: 10.37236/11602)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Molter, Henrik (2025) Counting temporal paths. Algorithmica, (doi: 10.1007/s00453-025-01301-3) (Early Online Publication)

2024

Davot, Tom, Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Madathil, Jayakrishnan and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2024) Temporal Triadic Closure: Finding Dense Substructures in Social Networks That Evolve Over Time. In: 39th AAAI Conference on Artificial Intelligence (AAAI-25), Philadelphia, PA, USA, 25 Feb - 04 Mar 2025, (Accepted for Publication)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Larios-Jones, Laura, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 (2024) Reachability in Temporal Graphs under Perturbation. In: 50th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2025), Bratislava, Slovakia, 20-23 Jan 2025, (Accepted for Publication)

Bressan, Marco, Goldberg, Leslie Ann, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Roth, Marc (2024) Counting subgraphs in somewhere dense graphs. SIAM Journal on Computing, 53(5), pp. 1409-1438. (doi: 10.1137/22M1535668)

Bocci, Christiano, Capresi, Chiara, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Sylvester, John ORCID: https://orcid.org/0000-0002-6543-2934 (2024) A new temporal interpretation of cluster editing. Journal of Computer and System Sciences, 144, 103551. (doi: 10.1016/j.jcss.2024.103551)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Hand, Samuel D., Larios-Jones, Laura ORCID: https://orcid.org/0000-0003-3322-0176 and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2024) Structural Parameters for Dense Temporal Graphs. In: 49th International Symposium on Mathematical Foundations of Computer Science, Bratislava, Slovakia, 26-30 Aug 2024, 52:1-52:15. ISBN 9783959773355 (doi: 10.4230/LIPIcs.MFCS.2024.52)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Lee, Duncan ORCID: https://orcid.org/0000-0002-6175-6800, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Sylvester, John ORCID: https://orcid.org/0000-0002-6543-2934 and Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 (2024) The complexity of finding and enumerating optimal subgraphs to represent spatial correlation. Algorithmica, (doi: 10.1007/s00453-024-01256-x) (Early Online Publication)

Dell, Holger, Lapinskas, John and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2024) Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs. In: 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2024), Tallinn, Estonia, 8-13 July 2024, (Accepted for Publication)

2023

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 and Sylvester, John (2023) Cops and robbers on multi-layer graphs. In: Graph-Theoretic Concepts in Computer Science:49th International Workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023, Revised Selected Papers. Series: Lecture notes in computer science (14093). Springer: Cham. ISBN 9783031433795 (Accepted for Publication)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Molter, Hendrik (2023) Counting Temporal Paths. In: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), Hamburg, Germany, 07-10 Mar 2023, p. 30. (doi: 10.4230/LIPIcs.STACS.2023.30)

Bumpus, Benjamin Merlin and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2023) Edge exploration of temporal graphs. Algorithmica, 85(3), pp. 688-716. (doi: 10.1007/s00453-022-01018-7)

Bressan, Marco, Goldberg, Leslie Ann, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Roth, Marc (2023) Counting Subgraphs in Somewhere Dense Graphs. In: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Cambridge, Massachusetts, USA, 10-13 January 2023, ISBN 9783959772631

2022

Groenland, Carla, Johnston, Tom, Kupavskii, Andrey, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Scott, Alex and Tan, Jane (2022) Reconstructing the degree sequence of a sparse graph from a partial deck. Journal of Combinatorial Theory, Series B, 157, pp. 283-293. (doi: 10.1016/j.jctb.2022.07.004)

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2022) Reducing reachability in temporal graphs: towards a more realistic model of real-world spreading processes. In: Computability in Europe: Revolutions and Revelations in Computability (CiE 2022), Swansea, UK, 11-15 Jul 2022, pp. 186-195. ISBN 9783031087394 (doi: 10.1007/978-3-031-08740-0_16)

Bocci, Cristiano, Capresi, Chiara, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Sylvester, John ORCID: https://orcid.org/0000-0002-6543-2934 (2022) A New Temporal Interpretation of Cluster Editing. In: 33rd International Workshop in Combinatorial Algorithms (IWOCA 2022), Trier, Germany, 07-09 Jun 2022, ISBN 9783031066771 (doi: 10.1007/978-3-031-06678-8_16)

Hand, Samuel D., Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292 and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2022) Making Life More Confusing for Firefighters. In: 11th International Conference on Fun with Algorithms (FUN 2022), Sicily, Italy, 30 May - 03 Jun 2022, ISBN 9783959772327 (doi: 10.4230/LIPIcs.FUN.2022.15)

Dell, Holger, Lapinskas, John and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2022) Approximately counting and sampling small witnesses using a colourful decision oracle. SIAM Journal on Computing, 51(4), pp. 849-899. (doi: 10.1137/19M130604X)

2021

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Mertzios, George B. and Zamaraev, Viktor (2021) Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119, pp. 60-77. (doi: 10.1016/j.jcss.2021.01.007)

Lee, Duncan ORCID: https://orcid.org/0000-0002-6175-6800, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 (2021) Improved inference for areal unit count data using graph-based optimisation. Statistics and Computing, 31(4), 51. (doi: 10.1007/s11222-021-10025-7)

Bumpus, Benjamin Merlin and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2021) Edge exploration of temporal graphs. In: 32nd International Workshop on Combinatorial Algorithms (IWOCA 2021), 05-07 Jul 2021, pp. 107-121. ISBN 9783030799861 (doi: 10.1007/978-3-030-79987-8_8)

Bonamy, Marthe and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2021) The interactive sum choice number of graphs. Discrete Applied Mathematics, 292, pp. 72-84. (doi: 10.1016/j.dam.2021.01.003)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Skerman, Fiona (2021) Assigning times to minimise reachability in temporal graphs. Journal of Computer and System Sciences, 115, pp. 169-186. (doi: 10.1016/j.jcss.2020.08.001)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Lee, Duncan ORCID: https://orcid.org/0000-0002-6175-6800, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 and Sylvester, John ORCID: https://orcid.org/0000-0002-6543-2934 (2021) The complexity of finding optimal subgraphs to represent spatial correlation. In: Du, Ding-Zhu, Du, Donglei, Wu, Chenchen and Xu, Dachuan (eds.) Combinatorial Optimization and Applications. Series: Lecture Notes in Computer Science (13135). Springer, pp. 152-166. ISBN 9783030926809 (doi: 10.1007/978-3-030-92681-6_13)

2020

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Rastegari, Baharak (2020) Solving hard stable matching problems involving groups of similar agents. Theoretical Computer Science, 844, pp. 171-194. (doi: 10.1016/j.tcs.2020.08.017)

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Skerman, Fiona (2020) The parameterised complexity of computing the maximum modularity of a graph. Algorithmica, 82, pp. 2174-2199. (doi: 10.1007/s00453-019-00649-7)

Dell, Holger, Lapinskas, John and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2020) Approximately Counting and Sampling Small Witnesses Using a Colourful Decision Oracle. In: ACM-SIAM Symposium on Discrete Algorithms (SODA20), Salt Lake City, Utah, USA, 5-8 Jan 2020, pp. 2201-2211. (doi: 10.5555/3381089.3381224)

2019

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Vu, Dominik K. (2019) Extremal properties of flood-filling games. Discrete Mathematics and Theoretical Computer Science, 21(4), 12. (doi: 10.23638/DMTCS-21-4-11)

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2019) Randomised enumeration of small witnesses using a decision oracle. Algorithmica, 81(2), pp. 519-540. (doi: 10.1007/s00453-018-0404-y)

Blasius, Thomas, Friedrich, Tobias, Lischeid, Julius, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Schirneck, Martin (2019) Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling. In: 21st Workshop on Algorithm Engineering and Experiments (ALENEX 2019), San Diego, CA, USA, 7-8 Jan 2019, ISBN 9781611975499 (doi: 10.1137/1.9781611975499.11)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Mertzios, George B. and Zamaraev, Viktor (2019) Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks. In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), Aachen, Germany, 26-30 Aug 2019, p. 57. ISBN 9783959771177 (doi: 10.4230/LIPIcs.MFCS.2019.57)

2018

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Rastegari, Baharak (2018) Stable Marriage with Groups of Similar Agents. In: WINE 2018: The 14th Conference on Web and Internet Economics, Oxford, United Kingdom, 15-17 Dec 2018, pp. 312-326. ISBN 9783030046118 (doi: 10.1007/978-3-030-04612-5_21)

Wong, M. ORCID: https://orcid.org/0000-0002-5683-8684 and Meeks, K. ORCID: https://orcid.org/0000-0001-5299-3073 (2018) Inequalities, Gender and Online/Offline Networks. Researching Youth and Inequality in the Digital Age Mini-Symposium, Glasgow, UK, 27 Jul 2018.

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Treglown, Andrew (2018) On the complexity of finding and counting solution-free sets of integers. Discrete Applied Mathematics, 243, pp. 219-238. (doi: 10.1016/j.dam.2018.02.008)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292 and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2018) Deleting edges to restrict the size of an epidemic: a new application for treewidth. Algorithmica, 80(6), pp. 1857-1889. (doi: 10.1007/s00453-017-0311-7)

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Skerman, Fiona (2018) The Parameterised Complexity of Computing the Maximum Modularity of a Graph. In: 13th International Symposium on Parameterized and Exact Computation (IPEC 2018), Helsinki, Finland, 22-24 Aug 2018, ISBN 9783959770842 (doi: 10.4230/LIPIcs.IPEC.2018.9)

2017

Jerrum, Mark and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2017) The parameterised complexity of counting even and odd induced subgraphs. Combinatorica, 37(5), pp. 965-990. (doi: 10.1007/s00493-016-3338-5)

Bonamy, Marthe and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2017) The interactive sum choice number of graphs. Electronic Notes in Discrete Mathematics, 61, pp. 139-145. (doi: 10.1016/j.endm.2017.06.031)

2016

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Scott, Alexander (2016) The parameterised complexity of list problems on graphs of bounded treewidth. Information and Computation, 251, pp. 91-103. (doi: 10.1016/j.ic.2016.08.001)

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2016) Randomised Enumeration of Small Witnesses Using a Decision Oracle. In: 11th International Symposium on Parameterized and Exact Computation (IPEC 2016), Aarhus, Denmark, 24-26 Aug 2016, ISBN 9783959770231 (doi: 10.4230/LIPIcs.IPEC.2016.22)

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2016) The challenges of unbounded treewidth in parameterised subgraph counting problems. Discrete Applied Mathematics, 198, pp. 170-194. (doi: 10.1016/j.dam.2015.06.019)

2015

Jerrum, Mark and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2015) Some hard families of parameterised counting problems. ACM Transactions on Computation Theory, 7(3), 11. (doi: 10.1145/2786017)

Jerrum, Mark and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2015) The parameterised complexity of counting connected subgraphs and graph motifs. Journal of Computer and System Sciences, 81(4), pp. 702-716. (doi: 10.1016/j.jcss.2014.11.015)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292 and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2015) Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth. In: 9th Annual International Conference on Combinatorial Optimization and Applications (COCOA'15), Houston,TX, USA, 18-20 Dec 2015, pp. 574-585. ISBN 9783319266268 (doi: 10.1007/978-3-319-26626-8_42)

2014

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Scott, Alexander (2014) Spanning trees and the complexity of flood-filling games. Theory of Computing Systems, 54(4), pp. 731-753. (doi: 10.1007/s00224-013-9482-z)

2013

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Scott, Alexander (2013) The complexity of FREE-FLOOD-IT on 2xn boards. Theoretical Computer Science, 500, pp. 25-43. (doi: 10.1016/j.tcs.2013.06.010)

2012

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Scott, Alexander (2012) The complexity of flood-filling games on graphs. Discrete Applied Mathematics, 160(7-8), pp. 959-969. (doi: 10.1016/j.dam.2011.09.001)

Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 and Scott, Alexander (2012) Spanning Trees and the Complexity of Flood-Filling Games. In: Sixth International Conference on Fun with Algorithms (FUN 2012), Venice, Italy, 04-06 Jun 2012, pp. 282-292. ISBN 9783642303463 (doi: 10.1007/978-3-642-30347-0_28)

This list was generated on Sun Jun 15 07:21:54 2025 BST.

Jump to: Articles | Book Sections | Conference or Workshop Item | Conference Proceedings

Number of items: 48.

Articles

Bumpus, Benjamin Merlin and Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073 (2023) Edge exploration of temporal graphs. Algorithmica, 85(3), pp. 688-716. (doi: 10.1007/s00453-022-01018-7)

Book Sections

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 and Sylvester, John (2023) Cops and robbers on multi-layer graphs. In: Graph-Theoretic Concepts in Computer Science:49th International Workshop, WG 2023, Fribourg, Switzerland, June 28–30, 2023, Revised Selected Papers. Series: Lecture notes in computer science (14093). Springer: Cham. ISBN 9783031433795 (Accepted for Publication)

Enright, Jessica ORCID: https://orcid.org/0000-0002-0266-3292, Lee, Duncan ORCID: https://orcid.org/0000-0002-6175-6800, Meeks, Kitty ORCID: https://orcid.org/0000-0001-5299-3073, Pettersson, William ORCID: https://orcid.org/0000-0003-0040-2088 and Sylvester, John ORCID: https://orcid.org/0000-0002-6543-2934 (2021) The complexity of finding optimal subgraphs to represent spatial correlation. In: Du, Ding-Zhu, Du, Donglei, Wu, Chenchen and Xu, Dachuan (eds.) Combinatorial Optimization and Applications. Series: Lecture Notes in Computer Science (13135). Springer, pp. 152-166. ISBN 9783030926809 (doi: 10.1007/978-3-030-92681-6_13)

Conference or Workshop Item

Conference Proceedings