UTL Repository >
ISEG - Instituto Superior de Economia e Gestão / ISEG - School of Economics & Management Lisbon >
Biblioteca Francisco Pereira de Moura / Francisco Pereira de Moura Library >
BISEG - Teses de Doutoramento / Ph.D. Thesis >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10400.5/4705

Title: Cobertura com restrições de conexidade
Authors: Pinto, Leonor Santiago
Advisor: Cerdeira, Jorge Orestes Lasbarrères
Keywords: Problema da cobertura
grafos
conexidade
programação linear inteira
poliedros
Set covering
graphs
connectivity
integer programming
poly-topes
Issue Date: Dec-2004
Publisher: Instituto Superior de Economia e Gestão
Citation: 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.
Abstract: 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.
Description: Doutoramento em Matemática Aplicada à Economia e Gestão
URI: http://hdl.handle.net/10400.5/4705
Appears in Collections:DM - Teses de Doutoramento / Ph.D. Thesis
BISEG - Teses de Doutoramento / Ph.D. Thesis

Files in This Item:

File Description SizeFormat
TD-LALSP-2004.pdf4.6 MBAdobe PDFView/Open
Restrict Access. You can request a copy!
Statistics
FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpaceOrkut
Formato BibTex mendeley Endnote Logotipo do DeGóis 

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

 

 
Estamos no RCAAP Governo Português separator Ministério da Educação e Ciência   Fundação para a Ciência e a Tecnologia

Financiado por:

POS_C UE