Premium
On crossings, the Crossing Postman Problem, and the Rural Postman Problem
Author(s) -
Garfinkel Robert S.,
Webb Ian R.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199910)34:3<173::aid-net1>3.0.co;2-w
Subject(s) - generalization , enhanced data rates for gsm evolution , mathematical optimization , computer science , mathematics , routing (electronic design automation) , combinatorics , artificial intelligence , computer network , mathematical analysis
The Rural Postman Problem (RPP), on an undirected network, is a classic edge‐routing problem. The Crossing Postman Problem is a generalization which is introduced here. Results are presented on the structure of optimal solutions to both problems. A new formulation for RPP, based on these results, is given. © 1999 John Wiley & Sons, Inc. Networks 34: 173–180, 1999