Zobrazeno 1 - 10
of 249
pro vyhledávání: '"BONNET, ÉDOUARD"'
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
Autor:
Bonnet, Édouard1 (AUTHOR) edouard.bonnet@ens-lyon.fr, Giocanti, Ugo2 (AUTHOR) ugo.giocanti@ens-lyon.fr, de Mendez, Patrice Ossona3 (AUTHOR) patrice.ossona-de-mendez@ehess.fr, Simon, Pierre4 (AUTHOR) simon@math.berkeley.edu, Thomassé, Stéphan1 (AUTHOR) stephan.thomasse@ens-lyon.fr, Toruńczyk, Szymon5 (AUTHOR) szymtor@mimuw.edu.pl
Publikováno v:
Journal of the ACM. Jun2024, Vol. 71 Issue 3, p1-45. 45p.
