Imagen de Portada

Freeze-Tag is NP-hard in 2D with $L_1$ distance

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Silva, Lucas de Oliveira, Pedrosa, Lehilton Lelis Chaves
Formato:	Preprint
Publicado:	2025
Materias:	Computational Geometry Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Computing the EHZ capacity is NP-hard
por: Leipold, Karla, et al.
Publicado: (2024)

Computing $p$-presentation distances is hard
por: Bjerkevik, Håvard Bakke, et al.
Publicado: (2024)

On the hardness of finding normal surfaces
por: Burton, Benjamin A., et al.
Publicado: (2019)

Communication Complexity is NP-hard
por: Hirahara, Shuichi, et al.
Publicado: (2025)

An elementary proof that linking problems are hard
por: Cheng, Shannon, et al.
Publicado: (2025)

Complexity of 2D Snake Cube Puzzles
por: MIT Hardness Group, et al.
Publicado: (2024)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
por: Yang, Chao, et al.
Publicado: (2024)

Optimizing for aggressive-style strategies in Flesh and Blood is NP-hard
por: Romão, Leonardo Gasparini, et al.
Publicado: (2025)

NP-hardness of SVP in Euclidean Space
por: Wan, Daqing
Publicado: (2026)

Approximating 1-in-3 SAT by linearly ordered hypergraph 3-colouring is NP-hard
por: Krokhin, Andrei, et al.
Publicado: (2025)

The Parameterized Complexity of Geometric 1-Planarity
por: Firbas, Alexander
Publicado: (2026)

Pizza Sharing is PPA-hard
por: Deligkas, Argyrios, et al.
Publicado: (2020)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
por: Binnendyk, Eric
Publicado: (2025)

King Chasing Problem in Chinese Chess is NP-hard
por: Li, Chao, et al.
Publicado: (2026)

NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
por: Baraskar, Omkar, et al.
Publicado: (2024)

Prove Symbolic Regression is NP-hard by Symbol Graph
por: Song, Jinglu, et al.
Publicado: (2024)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
por: DeStefano, Zachary, et al.
Publicado: (2025)

Quantum Max-Cut is NP hard to approximate
por: Piddock, Stephen
Publicado: (2025)

Devil's Games and $\text{Q}\mathbb{R}$: Continuous Games complete for the First-Order Theory of the Reals
por: Meijer, Lucas, et al.
Publicado: (2025)

Data Debugging is NP-hard for Classifiers Trained with SGD
por: Guo, Zizheng, et al.
Publicado: (2024)

On Saxe's theorems about the complexity of the Distance Geometry Problem
por: Kupperschmitt, Maël, et al.
Publicado: (2025)

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

Minimum Selective Subset on Some Graph Classes
por: Manna, Bubai
Publicado: (2025)

Counting Triangulations of Fixed Cardinal Degrees
por: Chambers, Erin, et al.
Publicado: (2025)

Query-Efficient Fixpoints of $\ell_p$-Contractions
por: Haslebacher, Sebastian, et al.
Publicado: (2025)

Tighter Bounds for the Randomized Polynomial-Time Simplex Algorithm for Linear Programming
por: Gibor, Daniel
Publicado: (2025)

Realizing Metric Spaces with Convex Obstacles
por: Kisfaludi-Bak, Sándor, et al.
Publicado: (2025)

Minimum Selective Subset on Unit Disk Graphs and Circle Graphs
por: Manna, Bubai
Publicado: (2025)

On the complexity of embedding in graph products
por: Biedl, Therese, et al.
Publicado: (2023)

Geometric Bipartite Matching is in NC
por: Bhore, Sujoy, et al.
Publicado: (2024)

Constrained Boundary Labeling
por: Depian, Thomas, et al.
Publicado: (2024)

Recognizing Visibility Graphs of Polygons with Holes and Internal-External Visibility Graphs of Polygons
por: Boomari, Hossein, et al.
Publicado: (2018)

Pathways to Tractability for Geometric Thickness
por: Depian, Thomas, et al.
Publicado: (2024)

The Complexity of Drawing Graphs on Few Lines and Few Planes
por: Chaplick, Steven, et al.
Publicado: (2016)

On the complexity of covering points by guillotine cuts
por: Garijo, Delia, et al.
Publicado: (2026)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
por: Durand, Martin
Publicado: (2026)

Computing the Polytope Diameter is Even Harder than NP-hard (Already for Perfect Matchings)
por: Wulf, Lasse
Publicado: (2025)

Undecidability of Translational Tiling with Three Tiles
por: Yang, Chan, et al.
Publicado: (2024)

Translational Aperiodic Sets of 7 Polyominoes
por: Yang, Chao, et al.
Publicado: (2024)

The Borsuk number of a graph
por: Cáceres, José, et al.
Publicado: (2026)