Source author record

David Ellison

David Ellison appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

math.CO Cell Behavior Discrete Mathematics

Catalog footprint

What is connected

4works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

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.

preprint2022arXiv

Orienteering problem with time-windows and updating delay

The Orienteering Problem with Time Window and Delay (\OPTiWinD) is a variant of the online orienteering problem. A series of requests appear in various locations while a vehicle moves within the territory to serve them. Each request has a time window during which it can be served and a weight which describes its importance. There is also a minimum delay $T$ between successive requests. The objective is to find a path for the vehicles that maximises the sum of the weights of the requests served. We further assume that the length of each time window is equal to the diameter of the territory. We study the optimal performance and competitive ratio for the set of instances with $n$ requests. We obtain complete resolution for $T$ at least half of the diameter, small values of $T$ or small values of $n$, as well as partial results in the remaining cases.

preprint2022arXiv

Switching Checkerboards

In order to study $\mathbf{M}(R,C)$, the set of binary matrices with fixed row and column sums $R$ and $C$, we consider sub-matrices of the form $\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ and $\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$, called positive and negative checkerboard respectively. We define an oriented graph of matrices $G(R,C)$ with vertex set $\mathbf{M}(R,C)$ and an arc from $\mathbf{A}$ to $\mathbf{A'}$ indicates you can reach $\mathbf{A'}$ by switching a negative checkerboard in $\mathbf{A}$ to positive. We show that $G(R,C)$ is a directed acyclic graph and identify classes of matrices which constitute unique sinks and sources of $G(R,C)$. Given $\mathbf{A},\mathbf{A'}\in\mathbf{M}(R,C)$, we give necessary conditions and sufficient conditions on $\mathbf{M}=\mathbf{A'}-\mathbf{A}$ for the existence of a directed path from $\mathbf{A}$ to $\mathbf{A'}$. We then consider the special case of $\mathbf{M}(\mathcal D)$, the set of adjacency matrices of graphs with fixed degree distribution $\mathcal D$. We define $G(\mathcal D)$ accordingly by switching negative checkerboards in symmetric pairs. We show that $Z_2$, an approximation of the spectral radius $λ_1$ based on the second Zagreb index, is non-decreasing along arcs of $G(\mathcal D)$. Also, $\ll$ reaches its maximum in $\mathbf{M}(\mathcal D)$ at a sink of $G(\mathcal D)$. We provide simulation results showing that applying successive positive switches to an Erd\H os-Rényi graph can significantly increase $λ_1$.

preprint2015arXiv

Cell-cell communication enhances the capacity of cell ensembles to sense shallow gradients during morphogenesis

Collective cell responses to exogenous cues depend on cell-cell interactions. In principle, these can result in enhanced sensitivity to weak and noisy stimuli. However, this has not yet been shown experimentally, and, little is known about how multicellular signal processing modulates single cell sensitivity to extracellular signaling inputs, including those guiding complex changes in the tissue form and function. Here we explored if cell-cell communication can enhance the ability of cell ensembles to sense and respond to weak gradients of chemotactic cues. Using a combination of experiments with mammary epithelial cells and mathematical modeling, we find that multicellular sensing enables detection of and response to shallow Epidermal Growth Factor (EGF) gradients that are undetectable by single cells. However, the advantage of this type of gradient sensing is limited by the noisiness of the signaling relay, necessary to integrate spatially distributed ligand concentration information. We calculate the fundamental sensory limits imposed by this communication noise and combine them with the experimental data to estimate the effective size of multicellular sensory groups involved in gradient sensing. Functional experiments strongly implicated intercellular communication through gap junctions and calcium release from intracellular stores as mediators of collective gradient sensing. The resulting integrative analysis provides a framework for understanding the advantages and limitations of sensory information processing by relays of chemically coupled cells.

preprint2014arXiv

G-graphs Characterisation and Incidence Graphs

Graphs derived from groups are a widely studied class of graphs, motivated by their highly symmetric structure. In particular, G-graphs offer an easy and interesting alternative construction of semi-symmetric graphs. After recalling the main properties of these graphs, this papers gives an extended characterisation of G-graphs and develops the link between bipartite G-graphs and incidence graphs. It appears that these two classes of graphs have a wide overlapping despite having completely different constructions. We give partial answers to the problem of finding which complete simple graphs have a G-graph as their incidence graph.