On the longest flip sequence to untangle segments in the plane
From MaRDI portal
Publication:6091152
DOI10.1007/978-3-031-27051-2_10arXiv2210.12036OpenAlexW4324009855MaRDI QIDQ6091152
Yan Gerard, Bastien Rivier, Guilherme Dias da Fonseca
Publication date: 24 November 2023
Published in: WALCOM: Algorithms and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2210.12036
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Flip distance between triangulations of a simple polygon is NP-complete
- Flip distance between two triangulations of a point set is NP-complete
- On the solution of traveling salesman problems
- Flipping edges in triangulations
- Fréchet distance between two point sets
- Approximation hardness of Travelling Salesman via weighted amplifiers
- Flip distance to some plane configurations
- Introduction to reconfiguration
- The traveling salesman problem and its variations.
- Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP
- Flip distance between triangulations of a planar point set is APX-hard
- Transforming triangulations
- The complexity of change
- Approximating Shortest Connected Graph Transformation for Trees
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Switching Distance Between Graphs with the Same Degrees
- On the Swap-Distances of Different Realizations of a Graphical Degree Sequence
- The Perfect Matching Reconfiguration Problem
- Transforming Graphs with the Same Degree Sequence
- The Number of Flips Required to Obtain Non-crossing Convex Cycles
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph II. Uniqueness
- Complexity results on untangling red-blue matchings
This page was built for publication: On the longest flip sequence to untangle segments in the plane
