Zobrazeno 1 - 10
of 34
pro vyhledávání: '"Eric Sedgwick"'
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:
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:
SoCG 2019-35th International Symposium on Computational Geometry
SoCG 2019-35th International Symposium on Computational Geometry, Jun 2019, Portland, United States
SoCG 2019-35th International Symposium on Computational Geometry, Jun 2019, Portland, United States
We prove that deciding if a diagram of the unknot can be untangled using at most $k$ Riedemeister moves (where $k$ is part of the input) is NP-hard. We also prove that several natural questions regarding links in the $3$-sphere are NP-hard, including
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::db3b2c227e31b5e9f3c9bd9b259fb980
http://arxiv.org/abs/1810.03502
http://arxiv.org/abs/1810.03502
Publikováno v:
ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2020, 67 (4), pp.1-29. ⟨10.1145/3396593⟩
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States
Journal of the ACM (JACM)
Journal of the ACM (JACM), Association for Computing Machinery, 2020, 67 (4), pp.1-29. ⟨10.1145/3396593⟩
We prove that the problem of deciding whether a two- or three-dimensional simplicial complex embeds into R 3 is NP -hard. Our construction also shows that deciding whether a 3-manifold with boundary tori admits an S 3 filling is NP -hard. The former
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fa9a227eccd5ef164f80ab923baa7fb0
https://hal.archives-ouvertes.fr/hal-01649774
https://hal.archives-ouvertes.fr/hal-01649774
Publikováno v:
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::08debf75e2e5dccaebe817113ced5592
https://doi.org/10.1137/1.9781611975031.86
https://doi.org/10.1137/1.9781611975031.86
Autor:
Saul Schleimer, Eric Sedgwick, Stephan Tillmann, David Letscher, Dylan P. Thurston, Hsien-Chih Chang, Arnaud de Mesmay, Jeff Erickson
Publikováno v:
SODA
ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States
ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States
We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω(n2) moves are required in the worst case to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::350b6f24f3130135774fad30fbf4c4bd
https://doi.org/10.1137/1.9781611975031.8
https://doi.org/10.1137/1.9781611975031.8
Publikováno v:
A Journey Through Discrete Mathematics ISBN: 9783319444789
We show that Heegaard Genus ≤ g, the problem of deciding whether a triangulated 3-manifold admits a Heegaard splitting of genus less than or equal to g, is NP-hard. The result follows from a quadratic time reduction of the NP-complete problem CNF-S
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d57d554311208768e5cf1e2ae0f61933
https://doi.org/10.1007/978-3-319-44479-6_3
https://doi.org/10.1007/978-3-319-44479-6_3
Publikováno v:
Algorithmica. 60:609-626
We show that for every n there are two simple curves on the torus intersecting at least n times without the two curves folding or spiraling with respect to each other. On the other hand, two simple curves in a punctured plane that intersect at least
Publikováno v:
Journal of Knot Theory and Its Ramifications. 18:397-446
It is shown that given any link-manifold, there is an algorithm to decide if the manifold contains an embedded, essential planar surface; if it does, the algorithm will construct one. If a slope on the boundary of the link-manifold is given, there is
Autor:
Eric Sedgwick, Yoav Moriah
Publikováno v:
Topology and its Applications. 156:885-896
Little is known on the classification of Heegaard splittings for hyperbolic 3-manifolds. Although Kobayashi gave a complete classification of Heegaard splittings for the exteriors of 2-bridge knots, our knowledge of other classes is extremely limited