A new algorithm for the directed Chinese postman problem
type: Item
instance of: scholarly article
title: A new algorithm for the directed Chinese postman problem
zbMATH Open document ID: 0664.90090
DOI: 10.1016/0305-0548(88)90053-6
author: Yaxiong Lin
author: Yongchang Zhao
published in: Computers \& Operations Research
publication date: 1988-01-01T00:00:00Z
review text: The directed Chinese Postman Problem can be transformed into a minimum cost flow problem over a derived network, or be transformed into a transportation problem in which the coefficients are determined by a shortest path problem over an extended network. Based on the Complementary Slackness Theorem, this paper will present an algorithm for the directed Chinese Postman Problem, which can be applied directly to the original network and, compared with the existing algorithms, has a better computational complexity \(O(kn^ 2)\) where k depends on the structure of the network. The algorithm is extended to the directed m-CPP case.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4087455
zbMATH Keywords: directed Chinese Postman Problem
zbMATH Keywords: minimum cost flow problem
zbMATH Keywords: transportation problem
zbMATH Keywords: Complementary Slackness Theorem
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: 0305-0548(88)90053-6
OpenAlex ID: W1799058206
cites work: Networks and vehicle routing for municipal waste collection
cites work: The Chinese Postman Problem for Mixed Networks
cites work: Q3863425
cites work: Matching, Euler tours and the Chinese postman
cites work: Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
cites work: Q5519709
cites work: Q3346110
description: scientific article; zbMATH DE number 4087455