Utilize este identificador para referenciar este registo: http://hdl.handle.net/10400.5/4705
Título: Cobertura com restrições de conexidade
Autor: Pinto, Leonor Santiago
Orientador: Cerdeira, Jorge Orestes Lasbarrères
Palavras-chave: Problema da cobertura
grafos
conexidade
programação linear inteira
poliedros
Set covering
graphs
connectivity
integer programming
poly-topes
Data de Defesa: Dez-2004
Editora: Instituto Superior de Economia e Gestão
Citação: Pinto, Leonor Santiago. 2004. "Cobertura com restrições de conexidade". Tese de Doutoramento. Universidade Técnica de Lisboa. Instituto Superior de Economia e Gestão.
Resumo: Dado um grafo bipartido com classes de bipartição V e U, uma cobertura é um subconjunto C Ç V em que cada vértice de U é adjacente a pelo menos um vértice de C. 0 problema da cobertura procura uma cobertura de cardinalidade mínima. No contexto da selecção de reservas para a con¬servação de espécies, V é o conjunto de povoamentos passíveis de serem seleccionados para integrar a reserva, U o conjunto de espécies a proteger e as arestas descrevem as ocorrências das espécies nos povoamentos. Algumas coberturas apresentam, no entanto, configurações espaciais que não são ade¬quadas do ponto de vista conservacionista. Por razões de sustentabilidade a fragmentação é considerada um atributo indesejável. Assim, a conexidade tem um papel importante na protecção da biodiversidade e vários autores têm recentemente proposto algoritmos que incorporam a conexidade. Nesta dissertação considera-se a introdução explícita da conexidade no problema da cobertura, de forma a dar resposta a questões relevantes em biologia da conservação.
Given a bipartite graph with bipartition V and U, a cover is a subset C C V such that each node of U is adjacent to at least one node in C. The set cov¬ering problem seeks a minimum cardinality cover. In the context of reserve selection for conservation of species, V is a set of candidate sites from a re¬serve network, U is the set of species to be protected, and the edges describe which species are represented in each site. Some covers however may assume spatial configurations which are not adequate for conservational purposes. For sustainability reasons the fragmentation of existing natural habitats should be avoided. Thus, connectivity appears to be an important issue for persistence of biodiversity, and several authors have recently proposed algorithms which incorporate connectivity. We address the issue of explic¬itly introducing connectivity in the set covering problem, with relevance for conservation biology.
Descrição: Doutoramento em Matemática Aplicada à Economia e Gestão
URI: http://hdl.handle.net/10400.5/4705
Aparece nas colecções:BISEG - Teses de Doutoramento / Ph.D. Thesis
DM - Teses de Doutoramento / Ph.D. Thesis

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
TD-LALSP-2004.pdf4,6 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.