Complexidade de bem-cobertura sob parâmetros de distância para algumas classes de grafos

Página do item simplificado
dc.contributor.advisor-co1Nascimento, Julliano Rosa
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/8971175373328824pt_BR
dc.contributor.advisor1Santana, Márcia Rodrigues Cappelle
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/4638125536971138pt_BR
dc.contributor.referee1Santana, Márcia Rodrigues Cappelle
dc.contributor.referee2Nascimento, Julliano Rosa
dc.contributor.referee3Sampaio, Rudini Menezes
dc.contributor.referee4Souza, Uéverton dos Santos
dc.creatorSantos, Vinícius Gabriel
dc.creator.Latteshttp://lattes.cnpq.br/0823680543858356pt_BR
dc.date.accessioned2022-05-10T11:59:37Z
dc.date.available2022-05-10T11:59:37Z
dc.date.issued2022-04-18
dc.description.abstractLet G = (V (G), E (G)) be a graph. A set I ⊆ V (G) is independent when any pairs of vertices belonging to I are not adjacent in G. An independent set is maximal if it is not properly contained in any other independent set of G. A graph G is well-covered if every maximal independent set of G is maximum. Determining whether a graph is well-covered is a coNP-complete problem. We present a kernelization algorithm for the problem of determining the WELL-COVERAGE for distance graphs for a class Q. Also results related to the intractability of WELL-COVERAGE parameterized for distance of free graphs of Cl with l ≥5. And finally, the inexistence of a polynomial kernel for WELL-COVERAGE parameterized by distance for cluster.eng
dc.description.provenanceSubmitted by Marlene Santos (marlene.bc.ufg@gmail.com) on 2022-05-09T15:29:45Z No. of bitstreams: 2 Dissertação - Vinícius Gabriel Santos - 2022.pdf: 701714 bytes, checksum: 27fc45070d283d755ec78a3197939e03 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2022-05-10T11:59:37Z (GMT) No. of bitstreams: 2 Dissertação - Vinícius Gabriel Santos - 2022.pdf: 701714 bytes, checksum: 27fc45070d283d755ec78a3197939e03 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5)en
dc.description.provenanceMade available in DSpace on 2022-05-10T11:59:37Z (GMT). No. of bitstreams: 2 Dissertação - Vinícius Gabriel Santos - 2022.pdf: 701714 bytes, checksum: 27fc45070d283d755ec78a3197939e03 (MD5) license_rdf: 805 bytes, checksum: 4460e5956bc1d1639be9ae6146a50347 (MD5) Previous issue date: 2022-04-18en
dc.description.resumoSeja G = (V (G), E (G)) um grafo. Um conjunto I ⊆V (G) é independente quando quaisquer pares de vértices pertencentes a I não são adjacentes em G. Um conjunto independente é dito maximal se não está propriamente contido em nenhum outro conjunto independente de G. Um grafo G é bem-coberto se todo conjunto independente maximal de G é máximo. Determinar se um grafo é bem-coberto é um problema coNP-completo. Nós apresentamos um algoritmo de kernelização para o problema de determinar a BEM-COBERTURA para grafos distância para uma classe Q. Também resultados relacionados a intratabilidade da BEM-COBERTURA parametrizado para distância de grafos livres de Cl com l ≥5. E por fim a inexistência de um kernel polinomial para BEM-COBERTURA parametrizado por distância para clusterpt_BR
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESpt_BR
dc.identifier.citationSANTOS, V. G. Complexidade de bem-cobertura sob parâmetros de distância para algumas classes de grafos. 2022. 75 f. Dissertação (Mestrado em Ciência da Computação) - Universidade Federal de Goiás, Goiânia, 2022.pt_BR
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/12051
dc.languageporpt_BR
dc.publisherUniversidade Federal de Goiáspt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto de Informática - INF (RG)pt_BR
dc.publisher.initialsUFGpt_BR
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)pt_BR
dc.rightsAttribution-NonCommercial-NoDerivatives 4.0 International*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/*
dc.subjectTeoria dos Grafospor
dc.subjectComplexidade parametrizada e bem-coberturapor
dc.subjectGraph theoryeng
dc.subjectParameterized complexity and well-covered graphseng
dc.subject.cnpqCIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAOpt_BR
dc.titleComplexidade de bem-cobertura sob parâmetros de distância para algumas classes de grafospt_BR
dc.title.alternativeComplexity of eell-covered graphs under parameters of distanceeng
dc.typeDissertaçãopt_BR

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Dissertação - Vinícius Gabriel Santos - 2022.pdf
Tamanho:
685.27 KB
Formato:
Adobe Portable Document Format
Descrição:
Baixar
Licença do Pacote
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
license.txt
Tamanho:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Mestrado em Ciência da Computação (INF)