Maximilidade em Grafos de Fluxo Redutíveis
Autores
|
3878 |
1400,877
|
|
|
3879 |
1400,877
|
Informações:
Publicações do PESC
Título
Maximilidade em Grafos de Fluxo Redutíveis
Linha de pesquisa
Otimização
Tipo de publicação
Tese de Doutorado
Número de registro
Data da defesa
4/4/1997
Resumo
Este trabalho investiga o conceito de maximalidade aplicado a grafos de fluxo redutíveis, definindo e caracterizando os grafos de fluxo redutíveis-maximais. São estudadas diversas propriedades desta família, para a qual obtivemos duas caracterizações distintas: uma delas ligada a redutibilidade e a outra expressa em termos de um produto que definimos entre grafos de fluxo. É elaborado um algoritmo linear para reconhecimento, baseado na segunda caracterização e em propriedades relativas a caminhos hamiltonianos direcionados em grafos de fluxo redutíveis. São resolvidos, em tempo linear, dois problemas para a família: isomorfismo e obtenção de um conjunto de arestas de realimentação com cardinalidade mínima.
Abstract
In this work, maximal reducible flowgraphs are defhed and characterized. Several properties are studied for this famiiy. In particular, two distinct characterizations are obtained: one of them is strongly related to reducibility and the other is based on a product that we have defined between flowgraphs. A linear-time recognition algorithm is developed, based on the second characterization and on properties of directed hamiltonian paths in reducible flowgraphs. Two problems are solved for maximal reducible flowgraphs: isomorphism and fínding a feedback arc set with rninimum cardinality, both in linear time.
Arquivo