Problema de particionamento em subgrafos complementares: complexidade e convexidade

Página do item simplificado
dc.contributor.advisor-co1Coelho, Erika Morais Martins
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/9389487015938509eng
dc.contributor.advisor1Castonguay, Diane
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/4005898623592261eng
dc.contributor.referee1Castonguay, Diane
dc.contributor.referee2Coelho, Erika Morais Martins
dc.contributor.referee3Protti, Fábio
dc.contributor.referee4Szwarcfiter, Jayme Luiz
dc.contributor.referee5Pinto, Leizer de Lima
dc.creatorNascimento, Julliano Rosa
dc.creator.Latteshttp://lattes.cnpq.br/8971175373328824eng
dc.date.accessioned2019-11-18T12:32:30Z
dc.date.issued2019-11-11
dc.description.abstractIn this work, we introduce the PARTITION INTO COMPLEMENTARY SUBGRAPHS (COMP-SUB(Pi)) problem, which receives as input a graph H and an edge set property Pi, and the goal is determining whether is possible to decompose the graph H into complementary subgraphs G and \bar{G} such that the edge set M between G and \bar{G} satisfies property Pi. COMP-SUB(Pi) generalizes the recognition of complementary prisms problem, which is the case when Pi is a perfect matching between corresponding vertices of G and \bar{G}. When Pi is arbitrary, we show results for k-clique or k-independent set free graphs. On property P_\emptyset which considers M =\emptyset, we show that COMP-SUB(P_\emptyset) is GI-complete for chordal graphs, but can be solved efficiently for permutation, comparability, co- comparability and co-interval graphs. Furthermore, we obtain characterizations for some subclasses of chordal graphs. We also obtain results for Pi_{Kn,n} , the case when M has all the possible edges between G and \bar{G} and for Pi_{PERF}, the case which considers M as a perfect matching. In particular, we show that COMP-SUB(Pi_{PERF}) problem is GI-hard, and we obtain characterizations for this problem when the input graph H is a cograph, a chordal or a distance-hereditary graph. On the other hand, we address three parameters of the geodetic convexity for complementary prisms: the hull number, the geodetic number and the convexity number. We obtain results on the hull number for complementary prisms G\bar{G} when both G e \bar{G} are connected. On the second and third parameter, we show that the decision problems related to the geodetic number and convexity number are NP-complete even restricted to complementary prisms. We also establish lower bounds on the geodetic number for G\bar{G} when G or \bar{G} have simplicial vertices and we determine the convexity number for G\bar{G} when G is disconnected, or G is a cograph.eng
dc.description.provenanceSubmitted by Franciele Moreira (francielemoreyra@gmail.com) on 2019-11-14T15:36:47Z No. of bitstreams: 2 Tese - Julliano Rosa Nascimento - 2019.pdf: 1734348 bytes, checksum: 97feaaf3fc2f24ae8f21d4c930ebd422 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceApproved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2019-11-18T12:32:30Z (GMT) No. of bitstreams: 2 Tese - Julliano Rosa Nascimento - 2019.pdf: 1734348 bytes, checksum: 97feaaf3fc2f24ae8f21d4c930ebd422 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)eng
dc.description.provenanceMade available in DSpace on 2019-11-18T12:32:30Z (GMT). No. of bitstreams: 2 Tese - Julliano Rosa Nascimento - 2019.pdf: 1734348 bytes, checksum: 97feaaf3fc2f24ae8f21d4c930ebd422 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2019-11-11eng
dc.description.resumoNesta tese, introduzimos o problema PARTIÇÃO EM SUBGRAFOS COMPLEMENTARES (COMP- SUB(Pi)), que recebe como entrada um grafo H e uma propriedade de arestas Pi, e o objetivo é determinar se existe uma decomposição do grafo H em subgrafos complementares G e \bar{G} tal que o conjunto de arestas M entre G e \bar{G} satisfaça a propriedade Pi. COMP-SUB(Pi) generaliza o problema de reconhecimento dos prismas complementares, que é o caso quando Pi é um emparelhamento perfeito entre vértices correspondentes de G e \bar{G}. Para Pi uma propriedade arbitrária, mostramos resultados para grafos livres de k-clique ou k-conjunto independente. Sobre a propriedade Pi_\emptyset que considera M = \emptyset, mostramos que COMP-SUB(Pi_\emptyset) é GI-completo para grafos cordais, mas pode ser resolvido eficientemente para grafos de permutação, comparabilidade, co-comparabilidade e co-intervalo. Além disso, obtemos caracterizações para algumas subclasses de grafos cordais. Também obtemos resultados considerando Pi_{Kn,n} , o caso em que M possui todas as arestas possíveis entre G e \bar{G} e para Pi_{PERF}, o caso que considera M como um emparelhamento perfeito. Em particular, mostramos que o problema COMP-SUB(Pi_{PERF}) é GI-difícil e obtemos caracterizações para este problema quando o grafo H de entrada é um cografo, grafo cordal ou distância-hereditária. Por outro lado, também abordamos nesta tese três parâmetros da convexidade geodética para prismas complementares: o número envoltório, o número geodético e o número de convexidade. Obtemos resultados sobre o número envoltório para prismas complementares G\bar{G} quando ambos G e \bar{G} são conexos. Sobre o segundo e o terceiro parâmetro, mostramos que seus problemas de decisão são NP-completos mesmo restritos aos prismas complementares. Além disso, estabelecemos limites inferiores do número geodético de G\bar{G} quando G ou \bar{G} possuem vértices simpliciais e determinamos o número de convexidade de G\bar{G} quando G é desconexo ou G é um cografo.eng
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPESeng
dc.formatapplication/pdf*
dc.identifier.citationNASCIMENTO, J. R. Problema de particionamento em subgrafos complementares: complexidade e convexidade. 2019. 129 f. Tese (Doutorado em Ciência da Computação) - Universidade Federal de Goiás, Foiânia, 2019.eng
dc.identifier.urihttp://repositorio.bc.ufg.br/tede/handle/tede/10180
dc.languageporeng
dc.publisherUniversidade Federal de Goiáseng
dc.publisher.countryBrasileng
dc.publisher.departmentInstituto de Informática - INF (RG)eng
dc.publisher.initialsUFGeng
dc.publisher.programPrograma de Pós-graduação em Ciência da Computação (INF)eng
dc.rightsAcesso Aberto
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectParticionamento de grafospor
dc.subjectSubgrafos complementarespor
dc.subjectIsomorfismo de grafospor
dc.subjectConvexidade geodéticapor
dc.subjectPrismas complementarespor
dc.subjectGraph partitioningeng
dc.subjectComplementary subgraphseng
dc.subjectGraph isomorphismeng
dc.subjectGeodetic convexityeng
dc.subjectComplementary prismseng
dc.subject.cnpqCIENCIAS SOCIAIS APLICADAS::CIENCIA DA INFORMACAOeng
dc.titleProblema de particionamento em subgrafos complementares: complexidade e convexidadeeng
dc.title.alternativePartitioning a graph into complementary subgraphs: complexity and convexityeng
dc.typeTeseeng

Arquivos

Pacote Original
Agora exibindo 1 - 1 de 1
Nenhuma Miniatura disponível
Nome:
Tese - Julliano Rosa Nascimento - 2019.pdf
Tamanho:
1.65 MB
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:
2.11 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Baixar

Coleções

Doutorado em Ciência da Computação