Copertina

Slant/Gokigen Naname is NP-complete, and Some Variations are in P

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Lynch, Jayson, Spalding-Jamieson, Jack
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Discrete Mathematics Computational Geometry Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
di: Spalding-Jamieson, Jack
Pubblicazione: (2025)

Geometric Thickness of Multigraphs is $\exists \mathbb{R}$-complete
di: Förster, Henry, et al.
Pubblicazione: (2023)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
di: Dorfer, Joseph
Pubblicazione: (2026)

Edge Multiway Cut and Node Multiway Cut are NP-complete on subcubic graphs
di: Johnson, Matthew, et al.
Pubblicazione: (2022)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
di: Yang, Puhan, et al.
Pubblicazione: (2025)

Internally-Convex Drawings of Outerplanar Graphs in Small Area
di: Bekos, Michael A., et al.
Pubblicazione: (2025)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

Distance Approximating Minors for Planar and Minor-Free Graphs
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2025)

An algorithm for accurate and simple-looking metaphorical maps
di: Katsanou, Eleni, et al.
Pubblicazione: (2025)

On Tight Robust Coresets for $k$-Medians Clustering
di: Huang, Lingxiao, et al.
Pubblicazione: (2025)

Simple Compact Monotone Tree Drawings
di: Oikonomou, Anargyros, et al.
Pubblicazione: (2017)

Upward Pointset Embeddings of Planar st-Graphs
di: Alegria, Carlos, et al.
Pubblicazione: (2024)

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
di: Hengeveld, Simon, et al.
Pubblicazione: (2020)

From Tutte to Floater and Gotsman: On the Resolution of Planar Straight-line Drawings and Morphs
di: Di Battista, Giuseppe, et al.
Pubblicazione: (2021)

Freeze-Tag in $L_1$ has Wake-up Time Five
di: Bonichon, Nicolas, et al.
Pubblicazione: (2024)

A Polynomial Coreset for Furthest Neighbor in Planar Metrics
di: Kluk, Kacper, et al.
Pubblicazione: (2026)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
di: Fomin, Fedor V., et al.
Pubblicazione: (2026)

Recognizing Sumsets is NP-Complete
di: Abboud, Amir, et al.
Pubblicazione: (2024)

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\ell)$-Sparse Subgraphs
di: Madarasi, Péter
Pubblicazione: (2025)

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
di: Deák, Bence, et al.
Pubblicazione: (2025)

Implicit representations via the polynomial method
di: Cardinal, Jean, et al.
Pubblicazione: (2026)

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
di: Gribanov, D., et al.
Pubblicazione: (2023)

Framework for $\exists \mathbb{R}$-Completeness of Two-Dimensional Packing Problems
di: Abrahamsen, Mikkel, et al.
Pubblicazione: (2020)

Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
di: Gajjar, Kshitij, et al.
Pubblicazione: (2026)

O(1)-Distortion Planar Emulators for String Graphs
di: Chang, Hsien-Chih, et al.
Pubblicazione: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
di: Foucaud, Florent, et al.
Pubblicazione: (2023)

The Squishy Grid Problem
di: Cai, Zixi, et al.
Pubblicazione: (2025)

Quasi-Monte Carlo Beyond Hardy-Krause
di: Bansal, Nikhil, et al.
Pubblicazione: (2024)

Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time
di: Liu, Bowie, et al.
Pubblicazione: (2025)

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
di: Dakhno, Grigorii, et al.
Pubblicazione: (2024)

A Deterministic Bicriteria Approximation Algorithm for the Art Gallery Problem
di: Elbassioni, Khaled
Pubblicazione: (2025)

Bipartite Exact Matching in P
di: Du, Yuefeng
Pubblicazione: (2026)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
di: Hellmuth, Marc, et al.
Pubblicazione: (2023)

On Classifying Continuous Constraint Satisfaction Problems
di: Miltzow, Tillmann, et al.
Pubblicazione: (2021)

Mim-Width is paraNP-complete
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2025)

Unbent Collections of Orthogonal Drawings
di: Antić, Todor, et al.
Pubblicazione: (2025)

The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring
di: Inoue, Yuta, et al.
Pubblicazione: (2026)

Some variations of the secretary problem
di: Agrawal, Sarthak, et al.
Pubblicazione: (2026)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
di: Galby, Esther, et al.
Pubblicazione: (2025)

String Matching with a Dynamic Pattern
di: Monteiro, Bruno, et al.
Pubblicazione: (2025)