Zobrazeno 1 - 10
of 25
pro vyhledávání: '"Arnaud De Mesmay"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol vol. 26:2, Iss Discrete Algorithms (2024)
A matroid $M$ is an ordered pair $(E,I)$, where $E$ is a finite set called the ground set and a collection $I\subset 2^{E}$ called the independent sets which satisfy the conditions: (i) $\emptyset \in I$, (ii) $I'\subset I \in I$ implies $I'\in I$, a
Externí odkaz:
https://doaj.org/article/b7d8f1972a714d3bb745d56c9b0ce6f6
Autor:
Hsien-Chih Chang, Arnaud de Mesmay
Publikováno v:
SODA
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States. pp.747-766, ⟨10.1137/1.9781611975994.46⟩
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States. pp.747-766, ⟨10.1137/1.9781611975994.46⟩
We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time durin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41de1f1757980058cba982b6e9bfc83c
https://doi.org/10.1145/3558097
https://doi.org/10.1145/3558097
Publikováno v:
Symposium on Simplicity in Algorithms (SOSA) ISBN: 9781611977585
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a62b750b61010aa990483b951833ad4d
https://doi.org/10.1137/1.9781611977585.ch12
https://doi.org/10.1137/1.9781611977585.ch12
Given $x \in (\mathbb{R}_{\geq 0})^{\binom{[n]}{2}}$ recording pairwise distances, the METRIC VIOLATION DISTANCE (MVD) problem asks to compute the $\ell_0$ distance between $x$ and the metric cone; i.e., modify the minimum number of entries of $x$ to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bdd9e23260b797406f666fd3a9019e5b
Publikováno v:
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (4), pp.1-26. ⟨10.1145/3450704⟩
SoCG 2019-35th International Symposium on Computational Geometry
SoCG 2019-35th International Symposium on Computational Geometry, Jun 2019, Portland, OR, United States
35th International Symposium on Computational Geometry (SoCG 2019)
Journal of the ACM
Journal of the ACM (JACM), Association for Computing Machinery, 2021, 68 (4), pp.1-26. ⟨10.1145/3450704⟩
SoCG 2019-35th International Symposium on Computational Geometry
SoCG 2019-35th International Symposium on Computational Geometry, Jun 2019, Portland, OR, United States
35th International Symposium on Computational Geometry (SoCG 2019)
Journal of the ACM
We prove essentially tight lower bounds, conditionally to the Exponential Time Hypothesis, for two fundamental but seemingly very different cutting problems on surface-embedded graphs: the Shortest Cut Graph problem and the Multiway Cut problem. A cu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::866bd341eb3b8fc895297390742f4384
https://hal.archives-ouvertes.fr/hal-03432633
https://hal.archives-ouvertes.fr/hal-03432633
Autor:
Arnaud de Mesmay
Publikováno v:
Astérisque. 407:27-52
Un nœud est souvent represente par un diagramme de nœud, c'est-a-dire une projection sur deux dimensions, ou l'on indique a chaque croisement lequel des deux brins passe au-dessus de l'autre. Deux diagrammes representent alors le meme nœud si et s
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::e0c80efecd64078b8ef8ca8f22f43365
https://doi.org/10.24033/ast.1059
https://doi.org/10.24033/ast.1059
Autor:
Benjamin A. Burton, Hsien-Chih Chang, Maarten Löffler, Clément Maria, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Jonathan Spreer
We present three "hard" diagrams of the unknot. They require (at least) three extra crossings before they can be simplified to the trivial unknot diagram via Reidemeister moves in $\mathbb{S}^2$. Both examples are constructed by applying previously p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::895c2831a3b913c861fa45b6497de8af
http://arxiv.org/abs/2104.14076
http://arxiv.org/abs/2104.14076
Publikováno v:
Algorithms for Sensor Systems ISBN: 9783030892395
ALGOSENSORS
ALGOSENSORS 2021
ALGOSENSORS 2021, Sep 2021, Lisbonne, Portugal. ⟨10.1007/978-3-030-89240-1_5⟩
ALGOSENSORS
ALGOSENSORS 2021
ALGOSENSORS 2021, Sep 2021, Lisbonne, Portugal. ⟨10.1007/978-3-030-89240-1_5⟩
Coloring unit-disk graphs efficiently is an important problem in the global and distributed setting, with applications in radio channel assignment problems when the communication relies on omni-directional antennas of the same power. In this context
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ba57844b8a6a787fdcde660e68bf48db
https://doi.org/10.1007/978-3-030-89240-1_5
https://doi.org/10.1007/978-3-030-89240-1_5
Publikováno v:
Journal of Knot Theory and Its Ramifications
Journal of Knot Theory and Its Ramifications, World Scientific Publishing, 2020, 29 (06), pp.2050043. ⟨10.1142/S0218216520500431⟩
Journal of Knot Theory and Its Ramifications, World Scientific Publishing, 2020, 29 (06), pp.2050043. ⟨10.1142/S0218216520500431⟩
We show that determining the crossing number of a link is NP-hard. For some weaker notions of link equivalence, we also show NP-completeness.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::097d7c65d8d7b60582817db58b982bc1
http://arxiv.org/abs/1908.04073
http://arxiv.org/abs/1908.04073
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783030358013
Graph Drawing
Graph Drawing 2019
Graph Drawing 2019, Sep 2019, Prague, Czech Republic
Graph Drawing
Graph Drawing 2019
Graph Drawing 2019, Sep 2019, Prague, Czech Republic
It is well-known that both the pathwidth and the outer-planarity of a graph can be used to obtain lower bounds on the height of a planar straight-line drawing of a graph. But both bounds fall short for some graphs. In this paper, we consider two othe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6c87645ac74e51484bbba2469cf1a30e
https://doi.org/10.1007/978-3-030-35802-0_36
https://doi.org/10.1007/978-3-030-35802-0_36