Separating from the dominant of the spanning tree polytope

Autor:	Francisco Barahona
Rok vydání:	1992
Předmět:	Spanning tree Birkhoff polytope Applied Mathematics Shortest-path tree Maximum flow problem Polytope Graph theory Management Science and Operations Research Minimum spanning tree Industrial and Manufacturing Engineering Combinatorics Software Mathematics Minimum degree spanning tree
Zdroj:	Operations Research Letters. 12:201-203
ISSN:	0167-6377
Popis:	We study the separation problem for the partition inequalities that define the dominant of the spanning tree polytope of a graph G = (V, E). We show that a most violated inequality can be found by solving at most |V| maximum flow problems. Cunningham (1985) had solved this as a sequence of |E| maximum flow problems.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::f8fa261f5cec235e80910c392eb79c3c https://doi.org/10.1016/0167-6377(92)90045-5 Zobrazit plný text záznamu