𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the mixed Chinese postman problem

✍ Scribed by T.K. Ralphs

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
289 KB
Volume
14
Category
Article
ISSN
0167-6377

No coin nor oath required. For personal study only.

✦ Synopsis

The mixed Chinese postman problem is a version of the well-known Chinese postman problem in which the underlying graph consists of both directed and undirected edges. We give an integer linear programming formulation for this problem and then show that the extreme points of its linear relaxation polyhedron are all half-integral.

πŸ“œ SIMILAR VOLUMES

On crossings, the Crossing Postman Probl
On crossings, the Crossing Postman Problem, and the Rural Postman Problem
✍ Garfinkel, Robert S.; Webb, Ian R. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 125 KB πŸ‘ 1 views

The Rural Postman Problem (RPP), on an undirected network, is a classic edge-routing problem. The Crossing Postman Problem is a generalization which is introduced here. Results are presented on the structure of optimal solutions to both problems. A new formulation for RPP, based on these results, is

On the windy postman problem
On the windy postman problem
✍ Meigu Guan πŸ“‚ Article πŸ“… 1984 πŸ› Elsevier Science 🌐 English βš– 325 KB
On the max-cut problem for a planar, cub
On the max-cut problem for a planar, cubic, triangle-free graph, and the Chinese postman problem for a planar triangulation
✍ Carsten Thomassen πŸ“‚ Article πŸ“… 2006 πŸ› John Wiley and Sons 🌐 English βš– 109 KB πŸ‘ 2 views

## Abstract Every 3‐connected planar, cubic, triangle‐free graph with __n__ vertices has a bipartite subgraph with at least 29__n__/24β€‰βˆ’β€‰7/6 edges. The constant 29/24 improves the previously best known constant 6/5 which was considered best possible because of the graph of the dodecahedron. Example