Uma generalização do problema de seleção de vertices em digrafos

AUTOR(ES)

Arlene Fortunato Machado

DATA DE PUBLICAÇÃO

1991

RESUMO

Este trabalho apresenta um estudo de uma generalização de um problema de seleção de vértices em digrafos e propõe a resolução deste problema através de métodos iterativos, em que em cada iteração, um problema de seleção é resolvido. A importância deste problema é devida ao seu relacionamento com alguns problemas clássicos de otimização (designação, bemparelhamento bipartido de custo máximo, fluxo de custo mínimo). É também, apresentado um estudo para um problema de seleção de vértices de um digrafo, estabelecendo relações entre este problema e o de b-emparelhamento máximo bipartido. Algoritmos para os problemas de b-emparelhamento máximo bipartido, seleção de vértices e seleção de vértices generalizada são desenvolvidos. Os algoritmos apresentados para um mesmo problema são comparados entre si.

ASSUNTO(S)

programação linear algoritmos

Documentos Relacionados

• O problema de Lang e uma generalização dos Teoremas de Stäckel
• O Problema da k-Cobertura por Vértices: uma Implementação FPT no Modelo BSP/CGM
• Uma generalização de fatores em graficos
• Uma abordagem híbrida para o problema de seleção de fornecedores em cadeia de suprimentos
• Uma generalização do teorema de Ljusternik-Schnirelmann.