On the mixed Chinese postman problem (Q1319678): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0167-6377(93)90021-8 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2036619365 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Matching, Euler tours and the Chinese postman / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5514188 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximation Algorithms for Some Postman Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The mixed postman problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5519709 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A fundamental problem in vehicle routing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of edge traversing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3801316 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 14:39, 22 May 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