Results 11 to 20 of about 369,293 (294)
NP-completeness: A retrospective [PDF]
, 1997 For a quarter of a century now, NP-completeness has been computer science's favorite paradigm, fad, punching bag, buzzword, alibi, and intellectual export. This paper is a fragmentary commentary on its origins, its nature, its impact, and on the attributes that have made it so pervasive and contagious.
Christos H. Papadimitriou
openaire +2 more sources
k-L(2, 1)-labelling for planar graphs is NP-complete for k>=4 [PDF]
, 2009 A mapping from the vertex set of a graph G=(V,E) into an interval of integers {0,...,k} is an L(2,1)-labelling of G of span k if any two adjacent vertices are mapped onto integers that are at least 2 apart, and every two vertices with a common ...
Havet, F, Eggemann, N, Noble, S D
core +7 more sources
Complexity results for the gap inequalities for the max-cut problem [PDF]
, 2012 We prove several complexity results about the gap inequalities for the max-cut problem, including (i) the gap-1 inequalities do not imply the other gap inequalities, unless NP=Co NP; (ii) there must exist non-redundant gap inequalities with exponentially
Galli, Laura +2 more
core +5 more sources
CoRR, 2021 We prove that the 2017 puzzle game ZHED is NP-complete, even with just 1 tiles. Such a puzzle is defined by a set of unit-square 1 tiles in a square grid, and a target square of the grid. A move consists of selecting an unselected 1 tile and then filling the next unfilled square in a chosen direction from that tile (similar to Tipover and Cross ...
Sagnik Saha, Erik D. Demaine
openaire +3 more sources
NP-completeness of the Planar Separator Problems
Journal of Graph Algorithms and Applications, 2006 For a given graph G, the Separator Problem asks whether a vertex or edge set of small cardinality (or weight) exists whose removal partitions G into two disjoint graphs of approximately equal sizes.
Junichiro Fukuyama
doaj +1 more source
Theoretical Computer Science, 2022 Rikudo is a number-placement puzzle, where the player is asked to complete a Hamiltonian path on a hexagonal grid, given some clues (numbers already placed and edges of the path). We prove that the game is complete for NP, even if the puzzle has no hole.
Nguyen, Viet-Ha, Perrot, Kévin
openaire +5 more sources
Universal First-Order Logic is Superfluous for NL, P, NP and coNP [PDF]
Logical Methods in Computer Science, 2014 In this work we continue the syntactic study of completeness that began with the works of Immerman and Medina. In particular, we take a conjecture raised by Medina in his dissertation that says if a conjunction of a second-order and a first-order ...
Nerio Borges, Blai Bonet
doaj +1 more source
Journal of Graph Algorithms and Applications, 2020 Our objective is to discover the topology of an energy distribution network modeled by a flow digraph from which we know the set of arcs without identification of their extremities.
Wilfried Ehounou +4 more
doaj +1 more source
NP-Completeness of Minimal Width Unordered Tree Layout
Journal of Graph Algorithms and Applications, 2004 Tree layout has received considerable attention because of its practical importance. Arguably the most common drawing convention is the (ordered) layered tree convention for rooted trees in which the layout is required to preserve the relative order of a
Kim Marriott, Peter Stuckey
doaj +1 more source
The Voronoi game on graphs and its complexity
Journal of Graph Algorithms and Applications, 2011 The Voronoi game is a two-person game which is a model for a competitive facility location. The game is played on a continuous domain, and only two special cases (one-dimensional case and one-round case) are well investigated.
Sachio Teramoto +2 more
doaj +1 more source