The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Paciência Peg é um jogo de tabuleiro para um jogador. O objetivo do jogo é remover todos os pinos do tabuleiro, exceto um. Paciência Peg em gráficos é uma paciência Peg jogada em gráficos arbitrários. Um grafo é chamado solucionável se existir algum vértice s de modo que seja possível remover todos os pinos, exceto um, começando com s como o buraco inicial. Neste artigo, provamos que é NP-completo decidir se um grafo é solucionável ou não.
Kazushi ITO
The University of Electro-Communications
Yasuhiko TAKENAGA
The University of Electro-Communications
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Kazushi ITO, Yasuhiko TAKENAGA, "Solvability of Peg Solitaire on Graphs is NP-Complete" in IEICE TRANSACTIONS on Information,
vol. E106-D, no. 6, pp. 1111-1116, June 2023, doi: 10.1587/transinf.2022EDP7092.
Abstract: Peg solitaire is a single-player board game. The goal of the game is to remove all but one peg from the game board. Peg solitaire on graphs is a peg solitaire played on arbitrary graphs. A graph is called solvable if there exists some vertex s such that it is possible to remove all but one peg starting with s as the initial hole. In this paper, we prove that it is NP-complete to decide if a graph is solvable or not.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2022EDP7092/_p
Copiar
@ARTICLE{e106-d_6_1111,
author={Kazushi ITO, Yasuhiko TAKENAGA, },
journal={IEICE TRANSACTIONS on Information},
title={Solvability of Peg Solitaire on Graphs is NP-Complete},
year={2023},
volume={E106-D},
number={6},
pages={1111-1116},
abstract={Peg solitaire is a single-player board game. The goal of the game is to remove all but one peg from the game board. Peg solitaire on graphs is a peg solitaire played on arbitrary graphs. A graph is called solvable if there exists some vertex s such that it is possible to remove all but one peg starting with s as the initial hole. In this paper, we prove that it is NP-complete to decide if a graph is solvable or not.},
keywords={},
doi={10.1587/transinf.2022EDP7092},
ISSN={1745-1361},
month={June},}
Copiar
TY - JOUR
TI - Solvability of Peg Solitaire on Graphs is NP-Complete
T2 - IEICE TRANSACTIONS on Information
SP - 1111
EP - 1116
AU - Kazushi ITO
AU - Yasuhiko TAKENAGA
PY - 2023
DO - 10.1587/transinf.2022EDP7092
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E106-D
IS - 6
JA - IEICE TRANSACTIONS on Information
Y1 - June 2023
AB - Peg solitaire is a single-player board game. The goal of the game is to remove all but one peg from the game board. Peg solitaire on graphs is a peg solitaire played on arbitrary graphs. A graph is called solvable if there exists some vertex s such that it is possible to remove all but one peg starting with s as the initial hole. In this paper, we prove that it is NP-complete to decide if a graph is solvable or not.
ER -