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
- List of Algorithms in Graph Theory and Computer Science
- Chinese Postman Problem Complexity List
References
- ↑ 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.
- ↑ Guan, Meigu (1962). "Graphic programming using odd or even points". Chinese Mathematics.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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/.
- ↑ 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.
- ↑ 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.
 |
