In: IMA Journal of Numerical Analysis, 2018, vol. 38, no. 2, p. 921-954
|
In: Wetlands Ecology and Management, 2015, vol. 23, no. 2, p. 241-256
|
Thèse de doctorat : Università della Svizzera italiana, 2020 ; 2020INFO018.
The immune system has a critical role in diseases of primary importance such as infections and cancer. Hence, it represents a target for novel therapeutic strategies. However, the immune system relies on a complex network of cell-to-cell interactions which remains largely unknown, or difficult to be interpreted. The combination of experimental data with computational methods is of paramount...
|
In: European Journal of Operational Research, 2015, vol. 240, no. 2, p. 307-314
In this paper we present the Selective Graph Coloring Problem, a generalization of the standard graph col-oring problem as well as several of its possible applications. Given a graph with a partition of its vertex set into several clusters, we want to select one vertex per cluster such that the chromatic number of the subgraph induced by the selected vertices is minimum. This problem appeared...
|
In: Evolutionary Biology, 2020, p. -
The neck connects the head and the trunk and is the key structure allowing all movements of the head. The neck morphology of birds is the most variable among living tetrapods, including significant differences in the number and shape of the cervical vertebrae. Despite these differences, according to the literature, three morphofunctional regions (i.e., modules) have been identified along the...
|
In: 30th International Symposium on Algorithms and Computation (ISAAC) - Leibniz International Proceedings in Informatics, 2019, vol. 149, no. 21, p. 1-14
In this paper, we consider the following problem: given a connected graph G, can we reduce the domination number of G by one by using only one edge contraction? We show that the problem is NP-hard when restricted to {P6, P4 + P2}-free graphs and that it is coNP-hard when restricted to subcubic claw-free graphs and 2P3-free graphs. As a consequence, we are able to establish a complexity dichotomy...
|
In: 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) - LIPICS Vol. 138, 2019, p. 41:1-41:13
In this paper, we study the following problem: given a connected graph G, can we reduce the domination number of G by at least one using k edge contractions, for some fixed integer k >= 0? We show that for k <= 2, the problem is coNP-hard. We further prove that for k=1, the problem is W[1]-hard parameterized by the size of a minimum dominating set plus the mim-width of the input graph, and that...
|
In: Discrete Applied Mathematics, 2019, vol. 268, p. 102-111
The eccentricity of a vertex v in a graph G is the maximum distance between v and any other vertex of G. The diameter of a graph G is the maximum eccentricity of a vertex in G. The eccentric connectivity index of a connected graph is the sum over all vertices of the product between eccentricity and degree. Given two integers n and D with D ≤ n−1, we characterize those graphs which have...
|
In: Journal of Graph Algorithms and Applications, 2009, vol. 13, no. 2, p. 99-118
Starting from the basic problem of reconstructing a 2-dimensional im- age given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k = 3 colors is open. Variations and special cases are considered for the case k = 3 colors where the graph corresponding to the union of some color classes (for instance colors 1...
|
In: Discrete Applied Mathematics, 2011, vol. 159, no. 17, p. 1971-1995
Strongly perfect graphs have been studied by several authors (e.g. Berge and Duchet (1984) [1], Ravindra (1984) [12] and Wang (2006) [14]). In a series of two papers, the current paper being the first one, we investigate a fractional relaxation of strong perfection. Motivated by a wireless networking problem, we consider claw-free graphs that are fractionally strongly perfect in the complement....
|