Binary group and Chinese postman polyhedra |
| |
Authors: | Gilles Gastou Ellis L Johnson |
| |
Institution: | (1) Départment Stratégie et Management, Groupe ESSEC, Avenue de la Grande Ecole, B.P. 105, 95021 Cergy Pontoise, France;(2) IBM Thomas J. Watson Research Center, 10598 Yorktown Heights, NY, USA |
| |
Abstract: | A new proof of the characterization of the Chinese postman polyhedra is given. In developing this proof, a theorem of Gomory about homomorphic lifting of facets for group polyhedra is generalized to subproblems. Some results for the Chinese postman problem are generalized to binary group problems. In addition, a connection is made between Fulkerson's blocking polyhedra and a blocking pair of binary group problems. A connection is also developed between minors and lifting of facets for group problems. |
| |
Keywords: | Polyhedra Chinese Postman Binary Group Problems Binary Matroids Blocking Clutters |
本文献已被 SpringerLink 等数据库收录! |
|