Chinese Postman Problem Complexity List

From HandWiki
Short description: none

This is a list of computational complexities for different arc routing problems.

Complexity of the Chinese Postman (CP) Problem

CP variant Classical Complexity Approximation Parametrized complexity
Undirected [math]\displaystyle{ O(|V|^3) }[/math]-time algorithm[1]
Directed [math]\displaystyle{ O(|V|^3) }[/math]-time algorithm[1]

[math]\displaystyle{ O((|E|-|V|)|V|^2) }[/math]-time algorithm[2]

Mixed NP-complete[3]

[math]\displaystyle{ O(|V|^3) }[/math]-time solvable if each vertex has even degree[1]

[math]\displaystyle{ O(\max\{|V|^3,|A|(\max\{|A|,|E|\})^2\}) }[/math]-time factor 3/2[4] [math]\displaystyle{ O(2^{|E|}\cdot|V|^3) }[/math]-time algorithm[5]

In FPT with respect to |A|[5]

In XP with respect to treewidth[6]

Windy NP-complete[7]

P in some special cases[7][8]

Factor 3/2[9]
k-Hierarchical NP-complete[10]

[math]\displaystyle{ O(k|V|^4) }[/math]-time solvable if precedence relation linear

Min-sum k postmen [math]\displaystyle{ O(|V|^3) }[/math]-time algorithm with post office vertex,[11] otherwise NP-complete[12] In FPT with respect to k without post office vertex[13]
Min-max k postmen NP-complete[14] [math]\displaystyle{ O(|V|^3) }[/math]-time factor(2-1/k)[14]

See also

References

  1. ↑ 1.0 1.1 1.2 Edmonds, Jack; Johnson, Ellis L. (1973). "Matching, Euler tours and the Chinese postman". Mathematical Programming 5 (1): 88–124. doi:10.1007/bf01580113. ISSN 0025-5610. http://dx.doi.org/10.1007/bf01580113. 
  2. ↑ Yaxiong, Lin; Yongchang, Zhao (January 1988). "A new algorithm for the directed chinese postman problem". Computers & Operations Research 15 (6): 577–584. doi:10.1016/0305-0548(88)90053-6. ISSN 0305-0548. http://dx.doi.org/10.1016/0305-0548(88)90053-6. 
  3. ↑ Papadimitriou, Christos H. (July 1976). "On the complexity of edge traversing". Journal of the ACM 23 (3): 544–554. doi:10.1145/321958.321974. ISSN 0004-5411. http://dx.doi.org/10.1145/321958.321974. 
  4. ↑ Raghavachari, Balaji; Veerasamy, Jeyakesavan (January 1999). "A 3/2-Approximation Algorithm for the Mixed Postman Problem". SIAM Journal on Discrete Mathematics 12 (4): 425–433. doi:10.1137/s0895480197331454. ISSN 0895-4801. http://dx.doi.org/10.1137/s0895480197331454. 
  5. ↑ 5.0 5.1 Gutin, Gregory; Jones, Mark; Sheng, Bin (2014), "Parameterized Complexity of the k-Arc Chinese Postman Problem", Algorithms - ESA 2014 (Berlin, Heidelberg: Springer Berlin Heidelberg): pp. 530–541, doi:10.1007/978-3-662-44777-2_44, ISBN 978-3-662-44776-5, http://dx.doi.org/10.1007/978-3-662-44777-2_44, retrieved 2022-05-09 
  6. ↑ Fernandes, Cristina G.; Lee, Orlando; Wakabayashi, Yoshiko (January 2009). "Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width". Discrete Applied Mathematics 157 (2): 272–279. doi:10.1016/j.dam.2007.10.032. ISSN 0166-218X. http://dx.doi.org/10.1016/j.dam.2007.10.032. 
  7. ↑ 7.0 7.1 Guan, Meigu (September 1984). "On the windy postman problem". Discrete Applied Mathematics 9 (1): 41–46. doi:10.1016/0166-218x(84)90089-1. ISSN 0166-218X. http://dx.doi.org/10.1016/0166-218x(84)90089-1. 
  8. ↑ Win, Zaw (May 1989). "On the Windy Postman Problem on eulerian graphs". Mathematical Programming 44 (1–3): 97–112. doi:10.1007/bf01587080. ISSN 0025-5610. http://dx.doi.org/10.1007/bf01587080. 
  9. ↑ Veerasamy, Jeyakesavan (1999). Approximation algorithms for Postman problems (PhD thesis). University of Texas at Dallas.
  10. ↑ Dror, Moshe; Stern, Helman; Trudeau, Pierre (1987). "Postman tour on a graph with precedence relation on arcs". Networks 17 (3): 283–294. doi:10.1002/net.3230170304. ISSN 0028-3045. http://dx.doi.org/10.1002/net.3230170304. 
  11. ↑ "12th world computer congress— IFIP congress'92". Computers in Industry 20 (1): 124–126. January 1992. doi:10.1016/0166-3615(92)90137-c. ISSN 0166-3615. http://dx.doi.org/10.1016/0166-3615(92)90137-c. 
  12. ↑ Thomassen, Carsten (June 1997). "On the Complexity of Finding a Minimum Cycle Cover of a Graph". SIAM Journal on Computing 26 (3): 675–677. doi:10.1137/s0097539794267255. ISSN 0097-5397. http://dx.doi.org/10.1137/s0097539794267255. 
  13. ↑ Corberán, Ángel (2015). Arc Routing: Problems, Methods, and Applications. ISBN 978-1-61197-366-2. 
  14. ↑ 14.0 14.1 Frederickson, Greg N.; Hecht, Matthew S.; Kim, Chul E. (May 1978). "Approximation Algorithms for Some Routing Problems". SIAM Journal on Computing 7 (2): 178–193. doi:10.1137/0207017. ISSN 0097-5397. http://dx.doi.org/10.1137/0207017. 




Retrieved from "https://handwiki.org/wiki/index.php?title=Chinese_Postman_Problem_Complexity_List&oldid=2240347"