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

Computational Complexity of the Vertex-to-Point Conflict-Free Chromatic Art Gallery Problem Complexidade computacional do problema da galeria de arte cromática livre de conflitos de vértice a ponto

Chuzo IWAMOTO, Tatsuaki IBUSUKI

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O problema da galeria de arte é encontrar um conjunto de guardas que juntos possam observar todos os pontos do interior de um polígono P. Nós estudamos um cromático variante do problema, onde cada guarda recebe um dos k cores distintas. Diz-se que uma proteção cromática é livre de conflitos se pelo menos uma das cores vistas por cada ponto P é único (ou seja, cada ponto em P é visto por algum guarda cuja cor aparece exatamente uma vez entre os guardas visíveis até aquele ponto). Neste artigo, consideramos vértice-a-ponto guarda, onde os guardas são colocados em vértices de P, e observam todos os pontos do interior de P. O Problema de galeria de arte cromática sem conflito de vértice a ponto é encontrar um conjunto de guardas coloridas tal que (i) as guardas sejam colocadas Pvértices de, e (ii) qualquer ponto em P pode ver um guarda de uma cor única entre todos os guardas visíveis. Neste artigo, é mostrado que determinar se existe um conjunto de proteção de vértice cromático livre de conflito para um polígono com buracos é NP-difícil quando o número de cores é k= 2.

Publicação
IEICE TRANSACTIONS on Information Vol.E106-D No.9 pp.1499-1506
Data de publicação
2023/09/01
Publicitada
2023/05/31
ISSN online
1745-1361
DOI
10.1587/transinf.2022EDP7222
Tipo de Manuscrito
PAPER
Categoria
Fundamentos de Sistemas de Informação

autores

Chuzo IWAMOTO
  Hiroshima University
Tatsuaki IBUSUKI
  Hiroshima University

Palavra-chave