A note on formulations for the A-partition problem on hypergraphs

A note on formulations for the A-partition problem on hypergraphs

0.00 Avg rating0 Votes
Article ID: iaor20001794
Country: Netherlands
Volume: 90
Issue: 1/3
Start Page Number: 115
End Page Number: 133
Publication Date: Jan 1999
Journal: Discrete Applied Mathematics
Authors: ,
Keywords: graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.