ISSN:
1436-4646
Keywords:
Polyhedra
;
Chinese Postman
;
Binary Group Problems
;
Binary Matroids
;
Blocking Clutters
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582160