Katie Clinch
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Katie Clinch has a total of 24 co-authors. Here are the top co-authors by number of shared publications:
- Freddie Illingworth
Department of Mathematics University College London London UK
4 shared publications - Tony Huynh
Sapienza Università di Roma
3 shared publications - Abdallah Saffidine
Potassco Solutions Potsdam Germany
2 shared publications - Chris Manzie
Department of Electrical and Electronic Engineering, The University of Melbourne, Parkville, VIC, Australia
2 shared publications - David R. Wood
Monash University, Melbourne, Australia
2 shared publications - Jackson Goerner
Monash University
2 shared publications
Latest Publications
- Open Access
- 14 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1070
A piecewise approach for the analysis of exact algorithms
- 14 February 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1070
Open AccessA piecewise approach for the analysis of exact algorithms
- 21 February 2025
- Published by Springer Nature
- p. 79-93
A Piecewise Approach for the Analysis of Exact Algorithms
- 21 February 2025
- Published by Springer Nature
- p. 79-93
A Piecewise Approach for the Analysis of Exact Algorithms
- 2 June 2024
- Published by Springer Nature
- p. 171-185
Product Structure of Graph Classes with Bounded Treewidth
- 2 June 2024
- Published by Springer Nature
- p. 171-185
Product Structure of Graph Classes with Bounded Treewidth
- Open Access
- 7 December 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 33 (3) , 351-376
Product structure of graph classes with bounded treewidth
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$ , for every graph $G \in \mathcal{G}$ there is a graph $H$ with $\textrm{tw}(H) \leqslant c$ such that $G$ is isomorphic to a subgraph of $H \boxtimes K_{f(\textrm{tw}(G))}$ . We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth $3$ ; the class of $K_{s,t}$ -minor-free graphs has underlying treewidth $s$ (for $t \geqslant \max \{s,3\}$ ); and the class of $K_t$ -minor-free graphs has underlying treewidth $t-2$ . In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star.- 7 December 2023
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 33 (3) , 351-376
Open AccessProduct structure of graph classes with bounded treewidth
We show that many graphs with bounded treewidth can be described as subgraphs of the strong product of a graph with smaller treewidth and a bounded-size complete graph. To this end, define the underlying treewidth of a graph class $\mathcal{G}$ to be the minimum non-negative integer $c$ such that, for some function $f$ , for every graph $G \in \mathcal{G}$ there is a graph $H$ with $\textrm{tw}(H) \leqslant c$ such that $G$ is isomorphic to a subgraph of $H \boxtimes K_{f(\textrm{tw}(G))}$ . We introduce disjointed coverings of graphs and show they determine the underlying treewidth of any graph class. Using this result, we prove that the class of planar graphs has underlying treewidth $3$ ; the class of $K_{s,t}$ -minor-free graphs has underlying treewidth $s$ (for $t \geqslant \max \{s,3\}$ ); and the class of $K_t$ -minor-free graphs has underlying treewidth $t-2$ . In general, we prove that a monotone class has bounded underlying treewidth if and only if it excludes some fixed topological minor. We also study the underlying treewidth of graph classes defined by an excluded subgraph or excluded induced subgraph. We show that the class of graphs with no $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a subdivided star, and that the class of graphs with no induced $H$ subgraph has bounded underlying treewidth if and only if every component of $H$ is a star. - Open Access
- 6 September 2023
- Published by Elsevier in Automatica
- Vol. 158
Auction algorithm sensitivity for multi-robot task allocation
- 6 September 2023
- Published by Elsevier in Automatica
- Vol. 158
Open AccessAuction algorithm sensitivity for multi-robot task allocation
- Open Access
Auction algorithm sensitivity for multi-robot task allocation
We consider the problem of finding a low-cost allocation and ordering of tasks between a team of robots in a d-dimensional, uncertain, landscape, and the sensitivity of this solution to changes in the cost function. Various algorithms have been shown to give a 2-approximation to the MinSum allocation problem. By analysing such an auction algorithm, we obtain intervals on each cost, such that any fluctuation of the costs within these intervals will result in the auction algorithm outputting the same solution.
Open AccessAuction algorithm sensitivity for multi-robot task allocation
We consider the problem of finding a low-cost allocation and ordering of tasks between a team of robots in a d-dimensional, uncertain, landscape, and the sensitivity of this solution to changes in the cost function. Various algorithms have been shown to give a 2-approximation to the MinSum allocation problem. By analysing such an auction algorithm, we obtain intervals on each cost, such that any fluctuation of the costs within these intervals will result in the auction algorithm outputting the same solution.
- Open Access
Notes on Aharoni's rainbow cycle conjecture
In 2017, Ron Aharoni made the following conjecture about rainbow cycles in edge-coloured graphs: If $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil \frac{n}{r} \rceil$. One motivation for studying Aharoni's conjecture is that it is a strengthening of the Caccetta-H\"aggkvist conjecture on digraphs from 1978. In this article, we present a survey of Aharoni's conjecture, including many recent partial results and related conjectures. We also present two new results. Our main new result is for the $r=3$ case of Aharoni's conjecture. We prove that if $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least 3, then $G$ contains a rainbow cycle of length at most $\frac{4n}{9}+7$. We also discuss how our approach might generalise to larger values of $r$.Open AccessNotes on Aharoni's rainbow cycle conjecture
In 2017, Ron Aharoni made the following conjecture about rainbow cycles in edge-coloured graphs: If $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least $r$, then $G$ contains a rainbow cycle of length at most $\lceil \frac{n}{r} \rceil$. One motivation for studying Aharoni's conjecture is that it is a strengthening of the Caccetta-H\"aggkvist conjecture on digraphs from 1978. In this article, we present a survey of Aharoni's conjecture, including many recent partial results and related conjectures. We also present two new results. Our main new result is for the $r=3$ case of Aharoni's conjecture. We prove that if $G$ is an $n$-vertex graph whose edges are coloured with $n$ colours and each colour class has size at least 3, then $G$ contains a rainbow cycle of length at most $\frac{4n}{9}+7$. We also discuss how our approach might generalise to larger values of $r$. - Open Access
- 16 November 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 325, 241-261
Global rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids
- 16 November 2022
- Published by Elsevier in Discrete Applied Mathematics
- Vol. 325, 241-261
Open AccessGlobal rigidity of 2-dimensional direction-length frameworks with connected rigidity matroids