On the mixed Chinese postman problem (Q1319678): Difference between revisions

Studied is the mixed Chinese postman problem in which the graph consists of both directed and undirected edges. Whereas in special cases, when the underlying graph is entirely directed or undirected the problem can be solved by an efficient algorithm in polynomial time, the mixed Chinese postman problem, being NP-complete, has an exponential time of solution. This problem is formulated as an integer linear programming problem with properties presented by three propositions and one theorem, the last being similar to a result first published in the Ph. D. Thesis of Zaw Win at the University of Augsburg, Germany (1987).