Results 1 to 10 of about 9,539 (164)
NP-Completeness Results for Minimum Planar Spanners [PDF]
Discrete Mathematics & Theoretical Computer Science, 1998 For any fixed parameter t greater or equal to 1, a \emph t-spanner of a graph G is a spanning subgraph in which the distance between every pair of vertices is at most t times their distance in G.
Ulrik Brandes, Dagmar Handke
doaj +3 more sources
Shellability is NP-complete [PDF]
Journal of the ACM, 2019 We prove that for every d ≥ 2, deciding if a pure, d -dimensional, simplicial complex is shellable is NP-hard, hence NP-complete. This resolves a question raised, e.g., by Danaraj and Klee in 1978. Our reduction also yields that for every d ≥ 2 and k
Xavier Goaoc +4 more
openaire +7 more sources
On subset sum problem in branch groups [PDF]
Groups, Complexity, Cryptology, 2020 We consider a group-theoretic analogue of the classic subset sum problem. In this brief note, we show that the subset sum problem is NP-complete in the first Grigorchuk group.
Andrey Nikolaev, Alexander Ushakov
doaj +1 more source
Contractibility and NP‐completeness [PDF]
Journal of Graph Theory, 1987 AbstractFor a fixed graph H, let H‐CON denote the problem of determining whether a given graph is contractible to H. The complexity of H‐CON is studied for H belonging to certain classes of graphs, together covering all connected graphs of order at most 4.
A.E. Brouwer (Andries), H.J. Veldman
openaire +2 more sources
LaserTank is NP-Complete [PDF]
, 2020 We show that the classical game LaserTank is $\mathrm{NP}$-complete, even when the tank movement is restricted to a single column and the only blocks appearing on the board are mirrors and solid blocks. We show this by reducing $3$-SAT instances to LaserTank puzzles.
Per Alexandersson, Petter Restadh
openaire +3 more sources
CoRR, 2020 In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an $m \times n$ grid of cells, where each cell possibly contains a clue among +, -, |. The goal is to partition the grid into disjoint rectangles, where every rectangle contains exactly one clue, rectangles containing + are square, rectangles containing - are strictly longer ...
Adler, Aviv +5 more
openaire +5 more sources
From NP-Completeness to DP-Completeness: A Membrane Computing Perspective
Complexity, 2020 Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ ...
Luis Valencia-Cabrera +4 more
doaj +1 more source
NP-completeness of slope-constrained drawing of complete graphs
Journal of Computational Geometry, 2020 We prove the NP-completeness of the following problem. Given a set $S$ of $n$ slopes and an integer $k\geq 1$, is it possible to draw a complete graph on $k$ vertices in the plane using only slopes from $S$? Equivalently, does there exist a set $K$ of
Cédric Pilatte
doaj +1 more source
Hard to Detect Factors of Univariate Integer Polynomials
Mathematics, 2023 We investigate the computational complexity of deciding whether a given univariate integer polynomial p(x) has a factor q(x) satisfying specific additional constraints.
Alberto Dennunzio +2 more
doaj +1 more source
Probabilistic Nearest Neighbors Classification
Entropy, 2023 Analysis of the currently established Bayesian nearest neighbors classification model points to a connection between the computation of its normalizing constant and issues of NP-completeness. An alternative predictive model constructed by aggregating the
Bruno Fava +2 more
doaj +1 more source