Source author record

Andrew McDowell

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Biomolecules Computational Engineering, Finance, and Science Data Structures and Algorithms

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Triangle-tilings in graphs without large independent sets

We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an $n$ -vertex graph $G$ with sublinear independence number. In this setting, we show that if $δ(G) \ge n/3 + o(n)$ then $G$ has a triangle-tiling covering all but at most four vertices. Also, for every $r \ge 5$ , we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that $G$ is $K_r$ -free and $n$ is divisible by $3$ .

preprint2014arXiv

DNA origami and the complexity of Eulerian circuits with turning costs

Building a structure using self-assembly of DNA molecules by origami folding requires finding a route for the scaffolding strand through the desired structure. When the target structure is a 1-complex (or the geometric realization of a graph), an optimal route corresponds to an Eulerian circuit through the graph with minimum turning cost. By showing that it leads to a solution to the 3-SAT problem, we prove that the general problem of finding an optimal route for a scaffolding strand for such structures is NP-hard. We then show that the problem may readily be transformed into a Traveling Salesman Problem (TSP), so that machinery that has been developed for the TSP may be applied to find optimal routes for the scaffolding strand in a DNA origami self-assembly process. We give results for a few special cases, showing for example that the problem remains intractable for graphs with maximum degree 8, but is polynomial time for 4-regular plane graphs if the circuit is restricted to following faces. We conclude with some implications of these results for related problems, such as biomolecular computing and mill routing problems.

preprint2013arXiv

Non-Vertex-Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn and Vu \cite{JKV} regarding threshold functions for the existence of an $H$ -factor in a random graph \gnp. We prove that the conjectured threshold function is correct for any graph $H$ which is not covered by its densest subgraphs. We also demonstrate that the main result of \cite{JKV} generalises to multigraphs, digraphs, and a multipartite model.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.