chinese_postman_problem (521B)
1 # Chinese postman problem 2 3 The [computational_problem] of computing the shortest [path] or [circuit] that visits every [edge] of a [graph] at least once 4 5 Can be posed for [graph_directed] or [graph_undirected] 6 7 [NP_complete] on: 8 - [Undirected_graphs] when traversal cost is different per direction: [windy_postman_problem] 9 - on [mixed_graphs]: [mixed_chinese_postman_problem] 10 - if only a subset of the edges are required 11 12 See also: [eulerian_path], [traveling_salesperson_problem] 13 14 Up: [computational_problem] on [graph]