Hello, I know that the Traveling Salesman Problem has a solution space of (n-1)! / 2 for n = nodes, when the symetrick TSP is considered. But, is there any mathematical way to show how big a solution space a Arc Routing Problem, like the Capacitated Arc Routing Problem have? Or any other way to show (describe) why ít is a complex problem? In all the literature it is only described as NP-hard, and thats it. Thanks

Hello, I know that the Traveling Salesman Problem has a solution space of (n-1)! / 2 for n = nodes, when the symetrick TSP is considered. But, is there any mathematical way to show how big a solution space a Arc Routing Problem, like the Capacitated Arc Routing Problem have? Or any other way to show (describe) why ít is a complex problem? In all the literature it is only described as NP-hard, and thats it. Thanks

Hello, How can I check if my graph stays connected, after removing one or more edges from it? I try to implement Christofides heuristik, and in some cases my code works (that is when the graph dosent disconnect under the process). Unlucky that is not the case for all the graphs. I use Dijkstras to check if there is a route from my last node in the edge I am to remove, to other nodes. But, how du I see that "this" edge if removed is disconnecting the graph, so I can leave the edge and try the next one? Thanks... It would be easier to understand if I could post a picture of the problem. :(