Please use this identifier to cite or link to this item:
http://repositorio.ufla.br/jspui/handle/1/48147
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.creator | Costa, Eurinardo | - |
dc.creator | Pessoa, Victor Lage | - |
dc.creator | Sampaio, Rudini | - |
dc.creator | Soares, Ronan | - |
dc.date.accessioned | 2021-09-16T17:59:02Z | - |
dc.date.available | 2021-09-16T17:59:02Z | - |
dc.date.issued | 2019-08-30 | - |
dc.identifier.citation | COSTA, 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.uri | http://repositorio.ufla.br/jspui/handle/1/48147 | - |
dc.description.abstract | In 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.language | en_US | pt_BR |
dc.publisher | Elsevier | pt_BR |
dc.rights | Attribution 4.0 International | * |
dc.rights | acesso aberto | pt_BR |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | * |
dc.source | Electronic Notes in Theoretical Computer Science | pt_BR |
dc.subject | Coloring game | pt_BR |
dc.subject | Game chromatic number | pt_BR |
dc.subject | Greedy coloring | pt_BR |
dc.subject | Grundy number | pt_BR |
dc.subject | PSPACE-hardness | pt_BR |
dc.subject | Jogos de colorir | pt_BR |
dc.subject | Número cromático do jogo | pt_BR |
dc.subject | Número Grundy | pt_BR |
dc.title | PSPACE-hardness of Two Graph Coloring Games | pt_BR |
dc.type | Artigo | pt_BR |
Appears in Collections: | DCC - Artigos publicados em periódicos |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
ARTIGO_PSPACE-hardness of Two Graph Coloring Games.pdf | 243,31 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
Admin Tools