Autores

2049
303,877,876
2050
303,877,876
2051
303,877,876

Informações:

Publicações do PESC

Título
Hipergrafos Direcionados
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
16/8/2001
Resumo

Este trabalho trata de hipergrafos direcionados, que são uma generalização de grafos direcionados. É feita uma reestruturação da teoria dos hipergrafos direcionados, que até então era formada por conceitos isolados e muitas vezes divergentes.

O conceito de planaridade de grafos é estendido para hipergrafos direcionados de uma forma bastante simples e direta, relacionando a planaridade de um hipergrafo direcionado com a planaridade de um grafo construído a partir do hipergrafo.

A classe dos hipergrafos redutíveis é apresentada como uma generalização dos grafos redutíveis. Para chegarmos nesta generalização, partimos das idéias originais de redutibilidade, usando o conceito de intervalos.

Com o objetivo de modelar o fluxo de controle de programas paralelos, a classe dos hipergrafos Serial-Paralelo-Disjunção é apresentada. É provado que um hipergrafo desta classe é redutível e apresentamos uma solução polinomial para o problema de encontrar um conjunto de vértices de realimentação (feedback vertex set) quando restrito a esta classe.

Abstract

This work studies directed hypergraphs, that generalize the concept of directed graphs (digraphs). The theoretical concepts about directed hypergraphs are organized in a well structured framework.
The concept of directed hypergraph planarity is presented based on the well known concept of graph planarity.
The class of reducible directed hypergraphs is presented as a generalization of reducible flow graphs. In arder to obtain such generalizaton the original ideas of contraction of intervals were used.
To model the contra flow of parallel programs, the class of Serial-Paralell-Disjunction hypergraphs are presented and proved to be reducible. A polinomial solution to the feedback vertex set problem when restricted to such class is presented.

Topo