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

Sunil Chopra*, Jonathan H. Owen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 languageEnglish (US)
Pages (from-to)115-133
Number of pages19
JournalDiscrete Applied Mathematics
Volume90
Issue number1-3
DOIs
StatePublished - Jan 15 1999

Keywords

  • Hypergraphs
  • Integer programming formulations
  • Partitions

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A note on formulations for the A-partition problem on hypergraphs'. Together they form a unique fingerprint.

Cite this