34 citations · 41 across the 8 of their papers we have counts for
12 papers
Half-integral linkages in highly connected directed graphs
Katherine Edwards, Irene Muzi, Paul Wollan
We study the half-integral -Directed Disjoint Paths Problem (kDDPP) in highly strongly connected digraphs. The integral kDDPP is NP-complete even when restricted to in…
Fast approximation algorithms for -centres in large -hyperbolic graphs
Katherine Edwards, W. Sean Kennedy, Iraj Saniee
We provide a quasilinear time algorithm for the -center problem with an additive error less than or equal to 3 times the input graph's hyperbolic constant. Specifically, for the…
On paths, stars and wyes in trees
Sébastien Bubeck, Katherine Edwards, Horia Mania +1
We further the study of local profiles of trees. Bubeck and Linial showed that the set of 5-profiles contains a certain polytope, namely the convex hull of d-millipedes, and they p…
Concentration of the number of solutions of random planted CSPs and Goldreich's one-way candidates
Emmanuel Abbe, Katherine Edwards
This paper shows that the logarithm of the number of solutions of a random planted -SAT formula concentrates around a deterministic -independent threshold. Specifically, if $…
Three-edge-colouring doublecross cubic graphs
Katherine Edwards, Daniel P. Sanders, Paul Seymour +1
A graph is apex if there is a vertex whose deletion makes the graph planar, and doublecross if it can be drawn in the plane with only two crossings, both incident with the infinite…
A relative of Hadwiger's conjecture
Katherine Edwards, Dong Yeap Kang, Jaehoon Kim +2
Hadwiger's conjecture asserts that if a simple graph has no minor, then its vertex set can be partitioned into stable sets. This is still open, but we prov…