On the mixed Chinese postman problem (Q1319678): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 03:55, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the mixed Chinese postman problem |
scientific article |
Statements
On the mixed Chinese postman problem (English)
0 references
12 May 1994
0 references
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).
0 references
half-integrality
0 references
mixed Chinese postman problem
0 references
integer linear programming
0 references