List of Graph Theory Problems

From HandWiki

This is a list of different problems in graph theory.

Problem Abbreviation Description Output Notes Examples
Arc Routing Problem ARP Determine a least-cost traversal of a specified arc subset of a graph, with or without constraints.[1] Seven Bridges of Konigsberg
Chinese Postman Problem CPP undirected graph G with Vertices V and weighted edges E Traverse every edge at least once with minimal cost "A mailman has to cover his assigned segment before returning to the post office. The problem is to find the shortest walking distance for the mailman."[2]
Rural Postman Problem RPP undirected graph G with Vertices V and weighted edges E Traverse a subset of the edges E at least once with minimum cost
Directed Rural Postman Problem DRPP
Rural Postman Problem with Turn Penalties RPP-TP, RPPTP
Windy Postman Problem WPP[3]
Windy Rural Postman Problem WRPP
Street Sweeper Problem SPP
m-Plowing Problem m-PP
Capacitated Plow Problem C-PP
Downhill Plow Problem DPP[4]
Downhill Plow Problem with Turn Penalties DPP-TP[5][6]
Rural Downhill Plow Problem with Turn Penalties RDPP-TP
Capacitated Arc Routing Problem CARP
k-Plow Windy Rural Postman Problem k-WRPP
Min-Max Downhill Plow Problem with Multiple Plows MM k-DPP
Min-Max Windy Rural Postman Problem MM k-WRPP
Plowing with Precedence Problem PPP
Min-Max Extended Downhill Plow Problem MM k-DPPE
Capacitated Chinese Postman Problem CCPP
Directed Chinese Postman Problem DCPP
Directed Rural Postman Problem DRPP
Extended Capacitated Arc Routing Problem ECARP
Hierarchical Chinese Postman Problem HCPP
Mixed Capacitated Arc Routing Problem MCARP
Mixed Chinese Postman Problem MCPP
Stacker Crane Problem SCP Certain arcs must be traversed at least once in one direction but can be traversed as many times in the other direction
Traveling Salesman Problem TSP
Undirected Capacitated Arc Routing Problem UCARP
Undirected Rural Postman Problem URPP
Vehicle Routing Problem VRP
Min-Max Multiple-Depot Rural Postman Problem MMMDRPP[7]
Generalized Vehicle Routing Problem GVRP[8]

See also

References

  1. ↑ Eiselt, H (May 1995). "Arc routing problems, part II: The rural postman problem". http://www.proquest.com/scholarly-journals/arc-routing-problems-part-ii-rural-postman/docview/219174102/se-2. 
  2. ↑ Guan, Meigu (1962). "Graphic programming using odd or even points". Chinese Mathematics. 
  3. ↑ Dussault, Benjamin; Golden, Bruce; Groër, Chris; Wasil, Edward (2013-04-01). "Plowing with precedence: A variant of the windy postman problem" (in en). Computers & Operations Research 40 (4): 1047–1059. doi:10.1016/j.cor.2012.10.013. ISSN 0305-0548. https://www.sciencedirect.com/science/article/pii/S0305054812002250. 
  4. ↑ Dussault, Benjamin; Golden, Bruce; Wasil, Edward (2014-10-01). "The downhill plow problem with multiple plows" (in en). Journal of the Operational Research Society 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 1476-9360. https://doi.org/10.1057/jors.2013.83. 
  5. ↑ Dussault, Benjamin; Golden, Bruce; Wasil, Edward (2014-10-01). "The downhill plow problem with multiple plows" (in en). Journal of the Operational Research Society 65 (10): 1465–1474. doi:10.1057/jors.2013.83. ISSN 1476-9360. https://doi.org/10.1057/jors.2013.83. 
  6. ↑ Dussualt, Benjamin (2012). "Modeling and solving arc routing problems in street sweeping and snow plowing". https://www.proquest.com/dissertations-theses/modeling-solving-arc-routing-problems-street/. 
  7. ↑ Chen, Huanfa; Cheng, Tao; Shawe-Taylor, John (2018-01-02). "A Balanced Route Design for Min-Max Multiple-Depot Rural Postman Problem (MMMDRPP): a police patrolling case". International Journal of Geographical Information Science 32 (1): 169–190. doi:10.1080/13658816.2017.1380201. ISSN 1365-8816. https://doi.org/10.1080/13658816.2017.1380201. 
  8. ↑ Ghiani, Gianpaolo; Improta, Gennaro (2000-04-01). "An efficient transformation of the generalized vehicle routing problem" (in en). European Journal of Operational Research 122 (1): 11–17. doi:10.1016/S0377-2217(99)00073-9. ISSN 0377-2217. https://www.sciencedirect.com/science/article/pii/S0377221799000739. 




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