Editing Chinese postman problem (section)

==Variants==
A few variants of the Chinese Postman Problem have been studied and shown to be [[NP-complete]].<ref>{{citation
 | last = Crescenzi
 | first = P. 
 |author2=Kann, V. |author3=Halldórsson, M. |author4=Karpinski, M. |author4-link=Marek Karpinski |author5=Woeginger, G |author5-link=Gerhard J. Woeginger | title = A compendium of NP optimization problems
 | publisher = KTH NADA, Stockholm
 | url = https://www.csc.kth.se/~viggo/problemlist/compendium.html
 | access-date = 2008-10-22
}}</ref>
*The windy postman problem is a variant of the route inspection problem in which the input is an undirected graph, but where each edge may have a different cost for traversing it in one direction than for traversing it in the other direction. In contrast to the solutions for directed and undirected graphs, it is [[NP-complete]].<ref>{{citation
 | last = Guan | first = Meigu | author-link = Meigu Guan
 | doi = 10.1016/0166-218X(84)90089-1
 | issue = 1
 | journal = [[Discrete Applied Mathematics]]
 | mr = 754427
 | pages = 41–46
 | title = On the windy postman problem
 | volume = 9
 | year = 1984| doi-access = free
 }}.</ref><ref name = "Complexity">{{citation|first1=J.K.|last1=Lenstra|first2=A.H.G.|last2=Rinnooy Kan|title=Complexity of vehicle routing and scheduling problems|journal=Networks|volume=11|issue=2|year=1981|pages=221–227|doi=10.1002/net.3230110211|url=http://ageconsearch.umn.edu/record/272191/files/erasmus119.pdf}}</ref>
* The [[Mixed Chinese postman problem]]: for this problem, some of the edges may be directed and can therefore only be visited from one direction. When the problem calls for a minimal traversal of a digraph (or multidigraph) it is known as the "New York Street Sweeper problem."<ref>{{citation|first1=Fred S.|last1=Roberts|first2=Barry|last2=Tesman|title=Applied Combinatorics|edition=2nd|year=2009|publisher=CRC Press|isbn=9781420099829|pages=642–645}}</ref>
* The ''k''-Chinese postman problem: find ''k'' cycles all starting at a designated location such that each edge is traversed by at least one cycle. The goal is to minimize the cost of the most expensive cycle.
* The "Rural Postman Problem": solve the problem with some edges not required.<ref name = "Complexity" />