Zobrazeno 1 - 10
of 144
pro vyhledávání: '"Bonnet, Edouard"'
Autor:
Bonnet, Édouard, Rzążewski, Paweł
We present a 1.8334-approximation algorithm for Vertex Cover on string graphs given with a representation, which takes polynomial time in the size of the representation; the exact approximation factor is $11/6$. Recently, the barrier of 2 was broken
Externí odkaz:
http://arxiv.org/abs/2409.18820
We study the complexity of the valued constraint satisfaction problem (VCSP) for every valued structure with the domain ${\mathbb Q}$ that is preserved by all order-preserving bijections. Such VCSPs will be called temporal, in analogy to the (classic
Externí odkaz:
http://arxiv.org/abs/2409.07285
A graph class admits an implicit representation if, for every positive integer $n$, its $n$-vertex graphs have a $O(\log n)$-bit (adjacency) labeling scheme, i.e., their vertices can be labeled by binary strings of length $O(\log n)$ such that the pr
Externí odkaz:
http://arxiv.org/abs/2409.04821
Autor:
Bonnet, Édouard, Huszár, Kristóf
Building on Whitney's classical method of triangulating smooth manifolds, we show that every compact $d$-dimensional smooth manifold admits a triangulation with dual graph of twin-width at most $d^{O(d)}$. In particular, it follows that every compact
Externí odkaz:
http://arxiv.org/abs/2407.10174
Autor:
Bonnet, Édouard
We present a simple, self-contained, linear reduction from 3-SAT to Treewidth. Specifically, it shows that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly requires $2^{\Omega(n)}$ time, unless the Exponential-Time Hypothesis
Externí odkaz:
http://arxiv.org/abs/2406.11628
Autor:
Bonnet, Édouard
Motivated by an induced counterpart of treewidth sparsifiers (i.e., sparse subgraphs keeping the treewidth large) provided by the celebrated Grid Minor theorem of Robertson and Seymour [JCTB '86] or by a classic result of Chekuri and Chuzhoy [SODA '1
Externí odkaz:
http://arxiv.org/abs/2405.13797
We introduce a dense counterpart of graph degeneracy, which extends the recently-proposed invariant symmetric difference. We say that a graph has sd-degeneracy (for symmetric-difference degeneracy) at most $d$ if it admits an elimination order of its
Externí odkaz:
http://arxiv.org/abs/2405.09011
Autor:
Bonnet, Édouard, Feghali, Carl, Nguyen, Tung, Scott, Alex, Seymour, Paul, Thomassé, Stéphan, Trotignon, Nicolas
In 1972, Mader showed that every graph without a 3-connected subgraph is 4-degenerate and thus 5-colorable}. We show that the number 5 of colors can be replaced by 4, which is best possible.
Comment: 13 pages
Comment: 13 pages
Externí odkaz:
http://arxiv.org/abs/2402.06338
A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ after vertex deletions and edge contractions. We show that for every $k$-vertex planar graph $H$, every graph $G$ excluding $H$ as an induced minor and $K_{t,t}$ as
Externí odkaz:
http://arxiv.org/abs/2312.07962
A class of graphs admits an adjacency labeling scheme of size $b(n)$, if the vertices in each of its $n$-vertex graphs can be assigned binary strings (called labels) of length $b(n)$ so that the adjacency of two vertices can be determined solely from
Externí odkaz:
http://arxiv.org/abs/2310.20522