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

Sunil Chopra; Jonathan H. Owen

doi:10.1016/S0166-218X(98)00087-0

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

Sunil Chopra^*, Jonathan H. Owen

^*Corresponding author for this work

Managerial Economics, Decision Sciences and Operations

Research output: Contribution to journal › Article › peer-review

4 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 language	English (US)
Pages (from-to)	115-133
Number of pages	19
Journal	Discrete Applied Mathematics
Volume	90
Issue number	1-3
DOIs	https://doi.org/10.1016/S0166-218X(98)00087-0
State	Published - Jan 15 1999

Keywords

Hypergraphs
Integer programming formulations
Partitions

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Access to Document

10.1016/S0166-218X(98)00087-0

Cite this

@article{380f8321d6134689abdd7b0763aa0acf,

title = "A note on formulations for the A-partition problem on hypergraphs",

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.",

keywords = "Hypergraphs, Integer programming formulations, Partitions",

author = "Sunil Chopra and Owen, {Jonathan H.}",

year = "1999",

month = jan,

day = "15",

doi = "10.1016/S0166-218X(98)00087-0",

language = "English (US)",

volume = "90",

pages = "115--133",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

number = "1-3",

}

TY - JOUR

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

AU - Chopra, Sunil

AU - Owen, Jonathan H.

PY - 1999/1/15

Y1 - 1999/1/15

N2 - 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.

AB - 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.

KW - Hypergraphs

KW - Integer programming formulations

KW - Partitions

UR - http://www.scopus.com/inward/record.url?scp=0042707007&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0042707007&partnerID=8YFLogxK

U2 - 10.1016/S0166-218X(98)00087-0

DO - 10.1016/S0166-218X(98)00087-0

M3 - Article

AN - SCOPUS:0042707007

SN - 0166-218X

VL - 90

SP - 115

EP - 133

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

IS - 1-3

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this