Abstract
Let H = (V,E) be an undirected hypergraph and A ⊆ V. We consider the problem of finding a minimum cost partition of V that separates every pair of nodes in A. We consider three formulations of the problem and show that the theoretical lower bounds to the integer optimal objective value provided by the LP-relaxations in all three cases are identical. We describe our empirical findings with each formulation.
Original language | English (US) |
---|---|
Pages (from-to) | 115-133 |
Number of pages | 19 |
Journal | Discrete Applied Mathematics |
Volume | 90 |
Issue number | 1-3 |
DOIs | |
State | Published - Jan 15 1999 |
Keywords
- Hypergraphs
- Integer programming formulations
- Partitions
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics