Matching 2-lattice polyhedra: Finding a maximum vector

Shiow Yun Chang; Donna C. Llewellyn; John H. Vande Vate

doi:10.1016/S0012-365X(00)00219-3

Matching 2-lattice polyhedra: Finding a maximum vector

Shiow Yun Chang, Donna C. Llewellyn, John H. Vande Vate

Institute for Inclusive and Transformative Scholarship

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

10 Scopus citations

Abstract

Matching 2-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, etc. In this paper we develop a polynomial-time extreme point algorithm for finding a maximum cardinality vector in a matching 2-lattice polyhedron.

Original language	English
Pages (from-to)	29-61
Number of pages	33
Journal	Discrete Mathematics
Volume	237
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(00)00219-3
State	Published - 28 Jun 2001

Keywords

Lattice polyhedra
Matching
Matroids
Polymatriods
Submodularity

Access to Document

10.1016/S0012-365X(00)00219-3

Cite this

@article{2d8fe9b8e74d41b8960e8d29f55583ad,

title = "Matching 2-lattice polyhedra: Finding a maximum vector",

abstract = "Matching 2-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, etc. In this paper we develop a polynomial-time extreme point algorithm for finding a maximum cardinality vector in a matching 2-lattice polyhedron.",

keywords = "Lattice polyhedra, Matching, Matroids, Polymatriods, Submodularity",

author = "Chang, \{Shiow Yun\} and Llewellyn, \{Donna C.\} and \{Vande Vate\}, \{John H.\}",

year = "2001",

month = jun,

day = "28",

doi = "10.1016/S0012-365X(00)00219-3",

language = "English",

volume = "237",

pages = "29--61",

number = "1-3",

}

TY - JOUR

T1 - Matching 2-lattice polyhedra

T2 - Finding a maximum vector

AU - Chang, Shiow Yun

AU - Llewellyn, Donna C.

AU - Vande Vate, John H.

PY - 2001/6/28

Y1 - 2001/6/28

N2 - Matching 2-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, etc. In this paper we develop a polynomial-time extreme point algorithm for finding a maximum cardinality vector in a matching 2-lattice polyhedron.

AB - Matching 2-lattice polyhedra are a special class of lattice polyhedra that include network flow polyhedra, fractional matching polyhedra, matroid intersection polyhedra, etc. In this paper we develop a polynomial-time extreme point algorithm for finding a maximum cardinality vector in a matching 2-lattice polyhedron.

KW - Lattice polyhedra

KW - Matching

KW - Matroids

KW - Polymatriods

KW - Submodularity

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

U2 - 10.1016/S0012-365X(00)00219-3

DO - 10.1016/S0012-365X(00)00219-3

M3 - Article

AN - SCOPUS:0035963548

SN - 0012-365X

VL - 237

SP - 29

EP - 61

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Matching 2-lattice polyhedra: Finding a maximum vector

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this