Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Guedes, Andre Luiz Pires, 1966- | - |
Autor(es): dc.contributor | Groshaus, Marina Esther | - |
Autor(es): dc.contributor | Universidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática | - |
Autor(es): dc.creator | Cruz, Edmilson Pereira da | - |
Data de aceite: dc.date.accessioned | 2025-09-01T11:30:26Z | - |
Data de disponibilização: dc.date.available | 2025-09-01T11:30:26Z | - |
Data de envio: dc.date.issued | 2024-12-02 | - |
Data de envio: dc.date.issued | 2024-12-02 | - |
Data de envio: dc.date.issued | 2023 | - |
Fonte completa do material: dc.identifier | https://hdl.handle.net/1884/93476 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/1884/93476 | - |
Descrição: dc.description | Orientador: André Luiz Pires Guedes | - |
Descrição: dc.description | Coorientador: Marina Groushaus | - |
Descrição: dc.description | Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa : Curitiba, 03/07/2024 | - |
Descrição: dc.description | Inclui referências | - |
Descrição: dc.description | Área de concentração: Ciência da Computação | - |
Descrição: dc.description | Resumo: Esta tese apresenta o estudo sobre propriedades estruturais de grafos biclique em termos de tipos de intersecção entre bicliques maximais. Mostramos que grafos de bicliques mutuamente inclusas de bigrafos de inclusão de intervalos são grafos de permutação e que todo grafo de permutação é subgrafo induzido do grafo de bicliques mutuamente inclusas de algum bigrafo de intervalos. Também provamos a presença de certos subgrafos induzidos para intersecções apenas por vértices, mutuamente inclusas e por aresta não-mutuamente inclusa em grafos bipartidos. Introduzimos o grafo de inclusão de partes de bicliques e uma subclasse dos grafos de comparabilidade que é equivalente à classe dos grafos de inclusão de partes de bicliques de grafos livres de triângulos, do qual nós derivamos uma caracterização da classe dos grafos biclique de grafos livres de triângulos. Nós também sugerimos um algoritmo para a computação de uma pré-imagem do grafo de bicliques mutuamente inclusas de um grafo livre de triângulos. Introduzimos bicliques diferenciadas por aresta e por não-aresta — os quais chamamos de propriedades diferenciadoras—e provamos que toda inclusão mútua é um tipo de diferenciação por não-aresta, que todo par de bicliques intersectantes são diferenciadas por aresta ou por não-aresta e que cada tipo de propriedade diferenciadora é equivalente à presença de algum subgrafo induzido. Analisamos o grafo biclique do join entre dois grafos à luz das propriedades estruturais nós cobrimos neste trabalho e apresentamos alguns outros resultados de interesse sobre o estudo de grafos biclique. | - |
Descrição: dc.description | Abstract: This thesis presents the study on structural properties of biclique graphs in terms of types of intersections between maximal bicliques. We show that the mutually included biclique graphs of interval containment bigraphs are permutation graphs and that every permutation graph is an induced subgraph of the mutually included biclique graph of some interval bigraph. We also prove the presence of certain induced subgraphs for vertex-only, mutually included and edge without mutual inclusion intersections in bipartite graphs. We introduce the inclusion graph of biclique parts of a graph and a subclass of comparability graphs that is equivalent to the class of inclusion graphs of biclique parts of triangle-free graphs, from which we derive a characterization of the class of biclique graphs of triangle-free graphs in terms of partially ordered sets. We also suggest an algorithm for the computation of a pre-image of the mutually included biclique graph of a triangle-free graph. We introduce the edge differentiated and non-edge differentiated bicliques—which we call the differentiated properties—and we prove the that every mutual inclusion is a type of differentiation by non-edge, that every pair of intersecting bicliques are differentiated by edge or non-edge, and that each type of differentiating property is equivalent to the presence of some induced subgraph. We analyze the biclique graph of a join between two graphs in light of the structutal properties we cover in this work and present some other results of interest on the study of biclique graphs. | - |
Formato: dc.format | 1 recurso online : PDF. | - |
Formato: dc.format | application/pdf | - |
Formato: dc.format | application/pdf | - |
Palavras-chave: dc.subject | Grafos (Sistema de computador) | - |
Palavras-chave: dc.subject | Ciência da Computação | - |
Título: dc.title | Propriedades estruturaus de grafos biclique | - |
Aparece nas coleções: | Repositório Institucional - Rede Paraná Acervo |
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: