Zobrazeno 1 - 10
of 18
pro vyhledávání: '"Caoduro, Marco"'
Grossman et al. show that the subdeterminants of the incidence matrix of a graph can be characterized using the graph's odd cycle packing number. In particular, a graph's incidence matrix is totally unimodular if and only if the graph is bipartite. W
Externí odkaz:
http://arxiv.org/abs/2411.10593
Autor:
Caoduro, Marco, Sebő, András
The boxicity of a graph is the smallest dimension $d$ allowing a representation of it as the intersection graph of a set of $d$-dimensional axis-parallel boxes. We present a simple general approach to determining the boxicity of a graph based on stud
Externí odkaz:
http://arxiv.org/abs/2309.02062
Autor:
Martínez, Virgina Ardévol, Caoduro, Marco, Feuilloley, Laurent, Narboni, Jonathan, Pournajafi, Pegah, Raymond, Jean-Florent
Publikováno v:
Theoretical Computer Science, Volume 971, 2023, 114068
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels:
Externí odkaz:
http://arxiv.org/abs/2208.14229
Autor:
Caoduro, Marco, Sebő, András
Given a finite family of squares in the plane, the packing problem asks for the maximum number $\nu$ of pairwise disjoint squares among them, while the hitting problem for the minimum number $\tau$ of points hitting all of them. Clearly, $\tau \ge \n
Externí odkaz:
http://arxiv.org/abs/2206.02185
We prove that for any triangle-free intersection graph of $n$ axis-parallel segments in the plane, the independence number $\alpha$ of this graph is at least $\alpha \ge n/4 + \Omega(\sqrt{n})$. We complement this with a construction of a graph in th
Externí odkaz:
http://arxiv.org/abs/2205.15189
Autor:
Caoduro, Marco, Lichev, Lyuben
An axis-parallel $d$-dimensional box is a cartesian product $I_1\times I_2\times \dots \times I_b$ where $I_i$ is a closed sub-interval of the real line. For a graph $G = (V,E)$, the $boxicity \ of \ G$, denoted by $\text{box}(G)$, is the minimum dim
Externí odkaz:
http://arxiv.org/abs/2105.02516
Autor:
Caoduro, Marco
Let $\mathcal{R}$ be a family of axis-parallel rectangles in the plane. The transversal number $\tau(\mathcal{R})$ is the minimum number of points needed to pierce all the rectangles. The independence number $\nu(\mathcal{R})$ is the maximum number o
Externí odkaz:
http://arxiv.org/abs/2012.13201
Autor:
Ardévol Martínez, Virginia, Caoduro, Marco, Feuilloley, Laurent, Narboni, Jonathan, Pournajafi, Pegah, Raymond, Jean-Florent
Publikováno v:
In Theoretical Computer Science 6 September 2023 971
Autor:
Caoduro, Marco1 marco.caoduro@ubc.ca, Cslovjecsek, Jana2 jana.cslovjecsek@epfl.ch, Pilipczuk, Michał3 michal.pilipczuk@mimuw.edu.pl, Węgrzycki, Karol4,5 wegrzycki@cs.unisaarland.de
Publikováno v:
Journal of Computational Geometry. 2023, Vol. 14 Issue 1, p144-156. 13p.