wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

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]