In: Monatshefte für Mathematik, 2015, vol. 178, no. 2, p. 171-190
|
In: Probability Theory and Related Fields, 2015, vol. 163, no. 1-2, p. 89-121
|
In: Communications in Mathematical Physics, 2015, vol. 334, no. 3, p. 1649-1666
|
In: Annals of Combinatorics, 2015, vol. 19, no. 3, p. 513-543
|
Thèse de doctorat : Università della Svizzera italiana, 2021 ; 2021INFO005.
Many relevant discrete optimization problems are believed to be hard to solve efficiently (i.e. they cannot be solved in polynomial time unless P=NP). An approximation algorithm is one of the ways to tackle these hard optimization problems. These algorithms have polynomial running time and compute a feasible solution whose value is within a proven factor (approximation factor) of the optimal...
|
In: Advances in Mathematics, 2019, vol. 354, p. 106745
We study singular integral operators induced by 3-dimensional Calderón-Zygmund kernels in the Heisenberg group. We show that if such an operator is L2 bounded on vertical planes, with uniform constants, then it is also L2 bounded on all intrinsic graphs of compactly supported C1,α functions over vertical planes. In particular, the result applies to the operator R induced by the...
|
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: Graphs and Combinatorics, 2007, vol. 23, no. 1, p. 47-60
We consider the problem of finding in a graph a set R of edges to be colored in red so that there are maximum matchings having some prescribed numbers of red edges. For regular bipartite graphs with n nodes on each side, we give sufficient conditions for the existence of a set R with |R| = n + 1 such that perfect matchings with k red edges exist for all k, 0 ≤ k ≤ n. Given two integers p...
|
In: Networks, 2008, vol. 51, no. 4, p. 256-267
An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family equation image of chains Pi together with vectors h(Pi) = (h1, . . . , hik), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = hij. An interpretation in terms of scheduling is presented. We consider special cases of...
|
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...
|