wiki_research

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

chinese_postman_problem (605B)

      1 # Chinese postman problem
      2 
      3 https://en.wikipedia.org/wiki/Chinese_postman_problem
      4 
      5 The [computational_problem] of computing the shortest [path] or [circuit] that visits every [edge] of a [graph] at least once
      6 
      7 Can be posed for [graph_directed] or [graph_undirected]. It is [PTIME] in both cases
      8 
      9 [NP_complete] on:
     10 - [Undirected_graphs] when traversal cost is different per direction: [windy_postman_problem]
     11 - on [mixed_graphs]: [mixed_chinese_postman_problem]
     12 - if only a subset of the edges are required
     13 
     14 See also: [eulerian_path], [traveling_salesperson_problem]
     15 
     16 Up: [computational_problem] on [graph]