On Polyhedra Related to Even Factors
| Autor: | Márton Makai, Tamás Király |
|---|---|
| Rok vydání: | 2004 |
| Předmět: | |
| Zdroj: | Integer Programming and Combinatorial Optimization ISBN: 9783540221135 IPCO |
| DOI: | 10.1007/978-3-540-25960-2_31 |
| Popis: | As a common generalization of matchings and matroid intersection, W.H. Cunningham and J.F. Geelen introduced the notion of path-matching, which they generalized even further by introducing even factors of weakly symmetric digraphs. Later, a purely combinatorial approach to even factors was given by Gy. Pap and L. Szegő, who showed that the maximum even factor problem remains tractable in the class of hardly symmetric digraphs. The present paper shows a direct polyhedral way to derive weighted integer min-max formulae generalizing those previous results. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|