List of Graph Theory Problems

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

* List of Algorithms in Graph Theory and Computer Science
* Chinese Postman Problem Complexity List

## 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.

0.00

(0 votes)

|

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