Requiring Connectivity in the Set Covering Problem

J. Orestes Cerdeira () and Leonor S. Pinto ()
Additional contact information
J. Orestes Cerdeira: Univ. Técnica de Lisboa
Leonor S. Pinto: Univ. Técnica de Lisboa

Journal of Combinatorial Optimization, 2005, vol. 9, issue 1, No 3, 35-47

Abstract: Abstract Given a bipartite graph with bipartition V and W, a cover is a subset C $${\subseteq}$$ V such that each node of W is adjacent to at least one node in C. The set covering problem seeks a minimum cardinality cover. Set covering has many practical applications. In the context of reserve selection for conservation of species, V is a set of candidate sites from a reserve network, W 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. Indeed, for sustainability reasons the fragmentation of existing natural habitats should be avoided, since this is recognized as being disruptive to the species adapted to the habitats. Thus, connectivity appears to be an important issue for protection of biological diversity. We therefore consider along with the bipartite graph, a graph G with node set V, describing the adjacencies of the elements of V, and we look for those covers C $${\subseteq}$$ V for which the subgraph of G induced by C is connected. We call such covers connected covers. In this paper we introduce and study some valid inequalities for the convex hull of the set of incidence vectors of connected covers.

Keywords: set covering; graphs; connected components; integer polytopes (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-005-5482-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:9:y:2005:i:1:d:10.1007_s10878-005-5482-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-005-5482-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().