On the domination number of $t$-constrained de Bruijn graphs

Autor: Tiziana Calamoneri, Angelo Monti, Blerina Sinaimeri

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no 2, Iss Graph Theory (2022)

Motivated by the work on the domination number of directed de Bruijn graphs and some of its generalizations, in this paper we introduce a natural generalization of de Bruijn graphs (directed and undirected), namely $t$-constrained de Bruijn graphs, w

Externí odkaz: https://doaj.org/article/87d9a1d897184bf8a9299d3743519832

Some classes of graphs that are not PCGs

Autor: Rossella Petreschi, Pierluigi Baiocchi, Angelo Monti, Tiziana Calamoneri

Publikováno v: Theoretical Computer Science. 791:62-75

A graph $G=(V,E)$ is a pairwise compatibility graph (PCG) if there exists an edge-weighted tree $T$ and two non-negative real numbers $d_{min}$ and $d_{max}$, $d_{min} \leq d_{max}$, such that each node $u \in V$ is uniquely associated to a leaf of $

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::377a8542499737048e15eecb961e31a2
https://doi.org/10.1016/j.tcs.2019.05.017

String factorisations with maximum or minimum dimension

Autor: Blerina Sinaimeri, Angelo Monti

Publikováno v: Theoretical Computer Science
Theoretical Computer Science, 2020, 842, pp.65-73. ⟨10.1016/j.tcs.2020.07.029⟩
Theoretical Computer Science, Elsevier, 2020, 842, pp.65-73. ⟨10.1016/j.tcs.2020.07.029⟩

In this paper we consider two problems concerning string factorisation. Specifically given a string w and an integer k find a factorisation of w where each factor has length bounded by k and has the minimum (the F-Min-D problem) or the maximum (the F

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bbb10dd858e6a5ae1f443d70dc4ae151
https://inria.hal.science/hal-02955643/file/1912.10140.pdf

Co-divergence and tree topology

Autor: Angelo Monti, Tiziana Calamoneri, Blerina Sinaimeri

Publikováno v: Journal of Mathematical Biology
Journal of Mathematical Biology, 2019, 79 (3), pp.1149-1167. ⟨10.1007/s00285-019-01385-w⟩
Journal of Mathematical Biology, Springer Verlag (Germany), 2019, 79 (3), pp.1149-1167. ⟨10.1007/s00285-019-01385-w⟩

In reconstructing the common evolutionary history of hosts and parasites, the current method of choice is the phylogenetic tree reconciliation. In this model, we are given a host tree H, a parasite tree P, and a function [Formula: see text] mapping t

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::de74cb1f7b3e1dd33507b93071b77c99
https://pubmed.ncbi.nlm.nih.gov/31203388

On dynamic threshold graphs and related classes

Autor: Tiziana Calamoneri, Rossella Petreschi, Angelo Monti

This paper deals with the well known classes of threshold and difference graphs, both characterized by separators , i.e. node weight functions and thresholds. We design an efficient algorithm to find the minimum separator, and we show how to maintain

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::50a88587ab227f95212381a6f48985d7
http://hdl.handle.net/11573/1104495