1. RI UFLA
  2. Instituto de Ciências Exatas e Tecnológicas - ICET
  3. Departamento de Ciência da Computação - DCC
  4. DCC - Artigos publicados em periódicos
Use este identificador para citar ou linkar para este item: http://repositorio.ufla.br/jspui/handle/1/48147
Registro completo de metadados
Campo DCValorIdioma
dc.creatorCosta, Eurinardo-
dc.creatorPessoa, Victor Lage-
dc.creatorSampaio, Rudini-
dc.creatorSoares, Ronan-
dc.date.accessioned2021-09-16T17:59:02Z-
dc.date.available2021-09-16T17:59:02Z-
dc.date.issued2019-08-30-
dc.identifier.citationCOSTA, E. et al. PSPACE-hardness of Two Graph Coloring Games. Electronic Notes in Theoretical Computer Science, [S. l.], v. 346, p. 333-344, 30 Aug. 2019. DOI: 10.1016/j.entcs.2019.08.030.pt_BR
dc.identifier.urihttp://repositorio.ufla.br/jspui/handle/1/48147-
dc.description.abstractIn this paper, we answer a long-standing open question proposed by Bodlaender in 1991: the game chromatic number is PSPACE-hard. We also prove that the game Grundy number is PSPACE-hard. In fact, we prove that both problems (the graph coloring game and the greedy coloring game) are PSPACE-Complete even if the number of colors is the chromatic number. Despite this, we prove that the game Grundy number is equal to the chromatic number for several superclasses of cographs, extending a result of Havet and Zhu in 2013.pt_BR
dc.languageen_USpt_BR
dc.publisherElsevierpt_BR
dc.rightsAttribution 4.0 International*
dc.rightsacesso abertopt_BR
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/*
dc.sourceElectronic Notes in Theoretical Computer Sciencept_BR
dc.subjectColoring gamept_BR
dc.subjectGame chromatic numberpt_BR
dc.subjectGreedy coloringpt_BR
dc.subjectGrundy numberpt_BR
dc.subjectPSPACE-hardnesspt_BR
dc.subjectJogos de colorirpt_BR
dc.subjectNúmero cromático do jogopt_BR
dc.subjectNúmero Grundypt_BR
dc.titlePSPACE-hardness of Two Graph Coloring Gamespt_BR
dc.typeArtigopt_BR
Aparece nas coleções:DCC - Artigos publicados em periódicos

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
ARTIGO_PSPACE-hardness of Two Graph Coloring Games.pdf243,31 kBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Recomendar este item Visualizar estatísticas


Este item está licenciada sob uma Licença Creative Commons Creative Commons

Ferramentas do administrador