Análise de complexidade do problema de encontrar um subgrafo solução ótimo para grafos E/OU planares

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorSouza, Uéverton-
Autor(es): dc.contributorProtti, Fábio-
Autor(es): dc.contributorBravo, Raquel-
Autor(es): dc.creatorAlves, Mateus Rodrigues-
Data de aceite: dc.date.accessioned2024-07-11T18:31:20Z-
Data de disponibilização: dc.date.available2024-07-11T18:31:20Z-
Data de envio: dc.date.issued2023-09-26-
Data de envio: dc.date.issued2023-09-26-
Fonte completa do material: dc.identifierhttp://app.uff.br/riuff/handle/1/30594-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/772146-
Descrição: dc.descriptionUm grafo E/OU é um grafo direcionado acíclico com arestas ponderadas que contém uma única fonte onde a todo vértice é atribuído um rótulo f(v) ∈ {e, ou}. Um subgrafo solução H de um grafo E/OU deve conter a fonte e obedecer a seguinte regra: se um vértice com o rótulo e (respectivamente, ou) estiver em H então todas (respectivamente, exatamente uma) as suas arestas de saída devem pertencer a H. Este problema é conhecido ser NP-Difícil para grafos gerais, e neste trabalho analisaremos a complexidade deste problema quando o grafo de entrada possui a restrição de ser planar ou um grafo apex com exatamente um sumidouro, mostrando que o problema permanece NP-Difícil mesmo em ambos os casos, mas FPT com relação a treewidth do grafo de entrada ou quando parametrizado pelo valor da solução desejada-
Descrição: dc.descriptionAn AND/OR graph is an acyclic directed graph with weighted edges that contains a single source where every vertex is assigned a label f(v) ∈ {e, or}. A subgraph solution H of an AND/OR graph must contain the source and obey the following rule: if a vertex of type and (respectively, or ) is in H then all (respectively, exactly one) its output edges must belong to H. This problem is known being NP-Hard for general graphs, and in this paper we will analyse the complexity of this problem when the input graph has the constraint of being planar or a apex graph with exactly one sync, showing that the problem remains NP-Hard in both cases, but is FPT with relation to treewidth of the input graph or parameterized by the value of the desired solution-
Descrição: dc.description35 p.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Direitos: dc.rightsOpen Access-
Direitos: dc.rightsCC-BY-SA-
Palavras-chave: dc.subjectGrafos E/OU-
Palavras-chave: dc.subjectGrafo Planar-
Palavras-chave: dc.subjectGrafo Apex-
Palavras-chave: dc.subjectNP-Dificuldade-
Palavras-chave: dc.subjectFPT-
Palavras-chave: dc.subjectTreewidth-
Palavras-chave: dc.subjectGrafo-
Palavras-chave: dc.subjectDecomposição em árvore-
Palavras-chave: dc.subjectComplexidade-
Palavras-chave: dc.subjectAND/OR-Graphs-
Palavras-chave: dc.subjectPlanar Graphs-
Palavras-chave: dc.subjectApex Graphs-
Palavras-chave: dc.subjectNP-Hardness-
Título: dc.titleAnálise de complexidade do problema de encontrar um subgrafo solução ótimo para grafos E/OU planares-
Tipo de arquivo: dc.typeTrabalho de conclusão de curso-
Aparece nas coleções:Repositório Institucional da Universidade Federal Fluminense - RiUFF

Não existem arquivos associados a este item.