Skip to main content
Software Engineering

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

8
  • 2
    My intuition says this might be a rather difficult problem. I've done some work on a similar problem, where there should be a toll on every segment, not just on the paths between specific endpoints. Since the number of nodes was in the thousands and the graph was highly connected, brute force was out of the question and we used various evolutionary algorithms to get a good enough placement. Your problem might be simpler, in particular if the graph is always a tree, as in your example. Commented Dec 12, 2017 at 18:17
  • Would you be looking for the longest common path between the set of given nodes then? Commented Dec 12, 2017 at 19:39
  • @A_A It's not necessarily a common path for the entire set. In the example graph, if I only have tolls for (A,B) and (D,C) then I would want the result to be [1] and [3]. If paths overlap for two tolls, then the result should be on that overlapping portion. Commented Dec 12, 2017 at 22:05
  • So, you would be looking for a) A "Servicing Node" between u,v \in G when the set of corresponding minimum distance paths contains no overlaps, b) The furthest/closest servicing node to u,v \in G when the set of corresponding minimum distance paths does contain overlaps. (?). It will be easier if we formulate what you are after first. Commented Dec 13, 2017 at 7:10
  • That's basically it, but I'd want all of the overlapping nodes that minimize the total number of service nodes. If a,b and c,d have no overlapping nodes, then I want a list of nodes between a,b and a separate list of nodes between c,d, since all are equally feasible service nodes. If a,b and c,d have overlapping nodes, then I'm looking for all overlapping nodes. Where I get stuck is in a larger graph. In the second example in my post, there can be a node that minimizes the total number of service nodes across multiple paths. Those are what I'm really after (if they exist). Commented Dec 13, 2017 at 17:11