Atenção: Todas as denúncias são sigilosas e sua identidade será preservada.
Os campos nome e e-mail são de preenchimento opcional
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Souza, Uéverton | - |
Autor(es): dc.contributor | Protti, Fábio | - |
Autor(es): dc.contributor | Bravo, Raquel | - |
Autor(es): dc.creator | Alves, Mateus Rodrigues | - |
Data de aceite: dc.date.accessioned | 2024-07-11T18:31:20Z | - |
Data de disponibilização: dc.date.available | 2024-07-11T18:31:20Z | - |
Data de envio: dc.date.issued | 2023-09-26 | - |
Data de envio: dc.date.issued | 2023-09-26 | - |
Fonte completa do material: dc.identifier | http://app.uff.br/riuff/handle/1/30594 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/772146 | - |
Descrição: dc.description | Um 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.description | An 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.description | 35 p. | - |
Formato: dc.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Direitos: dc.rights | Open Access | - |
Direitos: dc.rights | CC-BY-SA | - |
Palavras-chave: dc.subject | Grafos E/OU | - |
Palavras-chave: dc.subject | Grafo Planar | - |
Palavras-chave: dc.subject | Grafo Apex | - |
Palavras-chave: dc.subject | NP-Dificuldade | - |
Palavras-chave: dc.subject | FPT | - |
Palavras-chave: dc.subject | Treewidth | - |
Palavras-chave: dc.subject | Grafo | - |
Palavras-chave: dc.subject | Decomposição em árvore | - |
Palavras-chave: dc.subject | Complexidade | - |
Palavras-chave: dc.subject | AND/OR-Graphs | - |
Palavras-chave: dc.subject | Planar Graphs | - |
Palavras-chave: dc.subject | Apex Graphs | - |
Palavras-chave: dc.subject | NP-Hardness | - |
Título: dc.title | Análise de complexidade do problema de encontrar um subgrafo solução ótimo para grafos E/OU planares | - |
Tipo de arquivo: dc.type | Trabalho de conclusão de curso | - |
Aparece nas coleções: | Repositório Institucional da Universidade Federal Fluminense - RiUFF |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: