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

From MaRDI portal
Importer (talk | contribs)
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 / namelinks / 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
    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
    0 references
    0 references
    0 references
    0 references
    half-integrality
    0 references
    mixed Chinese postman problem
    0 references
    integer linear programming
    0 references
    0 references