Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus

A.M.H. Gerards

doi:10.1016/0167-6377(91)90038-Q

Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus

A.M.H. Gerards

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

8 Citations (Scopus)

Abstract

We extend a result of Barahona, saying that T-join and perfect matching problems for planar graphs can be formulated as linear programming problems using only a polynomial number of constraints and variables, to graphs embeddable on an arbitrary, but fixed, surface.

Original language	English
Pages (from-to)	377-382
Journal	Operations Research Letters
Volume	10
Issue number	7
DOIs	https://doi.org/10.1016/0167-6377(91)90038-Q
Publication status	Published - 1991

Access to Document

10.1016/0167-6377(91)90038-Q

Cite this

@article{b993b40158484296bd99ff2f3254add4,

title = "Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus",

abstract = "We extend a result of Barahona, saying that T-join and perfect matching problems for planar graphs can be formulated as linear programming problems using only a polynomial number of constraints and variables, to graphs embeddable on an arbitrary, but fixed, surface.",

author = "A.M.H. Gerards",

year = "1991",

doi = "10.1016/0167-6377(91)90038-Q",

language = "English",

volume = "10",

pages = "377--382",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier B.V.",

number = "7",

}

TY - JOUR

T1 - Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus

AU - Gerards, A.M.H.

PY - 1991

Y1 - 1991

N2 - We extend a result of Barahona, saying that T-join and perfect matching problems for planar graphs can be formulated as linear programming problems using only a polynomial number of constraints and variables, to graphs embeddable on an arbitrary, but fixed, surface.

AB - We extend a result of Barahona, saying that T-join and perfect matching problems for planar graphs can be formulated as linear programming problems using only a polynomial number of constraints and variables, to graphs embeddable on an arbitrary, but fixed, surface.

U2 - 10.1016/0167-6377(91)90038-Q

DO - 10.1016/0167-6377(91)90038-Q

M3 - Article

SN - 0167-6377

VL - 10

SP - 377

EP - 382

JO - Operations Research Letters

JF - Operations Research Letters

IS - 7

ER -

Compact systems for T-join and perfect matching polyhedra of graphs with bounded genus

Abstract

Access to Document

Fingerprint

Cite this