A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

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

Solvability of Peg Solitaire on Graphs is NP-Complete A solubilidade do Peg Solitaire em gráficos é NP-Completa

Kazushi ITO, Yasuhiko TAKENAGA

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

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.

Publicação
IEICE TRANSACTIONS on Information Vol.E106-D No.6 pp.1111-1116
Data de publicação
2023/06/01
Publicitada
2023/03/09
ISSN online
1745-1361
DOI
10.1587/transinf.2022EDP7092
Tipo de Manuscrito
PAPER
Categoria
Fundamentos de Sistemas de Informação

autores

Kazushi ITO
  The University of Electro-Communications
Yasuhiko TAKENAGA
  The University of Electro-Communications

Palavra-chave