Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/260203
Type: TESE
Degree Level: Doutorado
Title: Uma generalização do problema de seleção de vertices em digrafos
Author: Machado, Arlene Fortunato, 1941-
Advisor: Perin Filho, Clovis, 1947-
Abstract: 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

Abstract: A generalization of a vertex selection problem is presented and a resolution of this problem using an iterative method is proposed. A vertex selection problem is solved in each iteration of this method. The importance of this problem lies on its relationship to some classical optimization problems (assignment, maximum cost bipartite b-matching, minimum cost flow). A study of a vertex selection problem in a digraph is also presented. A relationship between this problem and the maximum bipartite b-matching problem is established. Algorithms to solve the maximum bipartite b-matching, the vertex selection and the generalized vertex selection problems are developed and the algorithms for each of the problems are compared.
Subject: Algoritmos
Programação linear
Language: Português
Editor: [s.n.]
Date Issue: 1991
Appears in Collections:FEEC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Machado_ArleneFortunato_D.pdf7.51 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.