I’m working on a problem that reduces to something like toll plaza placement on a set of highways. Given a large undirected graph and a list of node pairs with a toll value between them, I need to find the minimal set of toll plaza nodes that can levy the tolls (each plaza node can levy an arbitrary set of tolls). Each node would have a weight that defined how suitable it is to be a toll plaza.
This seems like a common algorithm, but I’ve never taken graph theory and my searches haven’t turned up much. Any pointers on how to solve this would be appreciated!
Graph: [A]----[1]-----[2]----[3]------[C] | | | | [B] [D]
For example, in this graph, if there are tolls for (A,D) and (B,C), the nodes 1,2,3 would all be equally suitable to levy the tolls, and I could pick one after sorting them by weight. If instead the toll list was:
(A,D) = 5 (B,D) = 6 (B,C) = 7 (A,B) = 1
Then [1] is the only single node that could levy all the tolls. Given lists like these, I want to find the set of “optimal” toll locations like this.