Search subgraph of maximum weight

Question

I have an urban area (let them think of it as a street graph), where all the streets have some weight and length associated with them. I want to find a connected set of streets located next to another, with max (or close to maximum) total weight W, given that my maximum subgraph can only contain up to N streets.

I’m not specifically interested in the subgraph that covers the entire schedule, but rather a small cluster of streets, maximum or close to the maximum combined weight, and where all the streets are located “next to” each other, where “next” it will be determined that no street is will be more than X meters from the center of the cluster. A suitable subgraph must be connected.

Does anyone know if a name exists for this algorithm, if it exists?

Also interested in any solutions, accurate or approximate.

To show this visually, suppose my graph is all street segments (intersection with intersection) in the image below. Thus, the individual street is not Avenue A, it is Avenue A between 10 and 11 and so on. The street will have a weight of 1 or 0. Suppose that the set of streets with the maximum weights is in the selected polygon - I want to find this polygon.

Answer 1

Here is a suggestion. Consider each vertex in the node graph as a "center" as you defined it. For each center C[i] perform Dijkstra's algorithm to construct the shortest path tree with C[i] as the source. Stop building the tree if it will include a vertex greater than the maximum allowed from the center.

Then let A[i] be the set of all edges connected with the vertices in the tree centered on V[i] . The result is a set A[i] with maximum weight.

The execution time of one execution of the Dijkstra algorithm is O(|E[i]| + |V[i]| log |V[i]|) for the ith center. Sets here are limited in size to the maximum distance from the center. The total cost sum_(i in 1..|V|) O(|E[i]| + |V[i]| log |V[i]|) . In the degenerate case, when the maximum allowable weight allows you to include the entire graph from each center, the cost will be O(|V| (|E| + |V| log |V|)) .

I might think of some possible optimizations to improve the runtime, but I want to make sure that this is due to the problem you are talking about.

Answer 2

Here is the whole programming exact formulation for the problem, assuming that you have a finite number of common streets, S, and the "center" of the cluster can be one of a finite number of streets S. If you look at the cluster center in a continuous Euclidean space, which will lead us to area problem Weber . This may be feasible, but we will have to look at the column generation formula .

An object function maximizes the weight of selected streets indexed with j . Constraint (1) indicates that exactly one center is selected. Constraint (2) indicates that for any potential center i only N streets are selected as neighbors. Restriction (3) provides that a street is selected as part of a district only if the corresponding center is selected. The rest are binary integer constraints.

If the street, chosen as the center, is considered one of the streets of N , it is easy to ensure it by indicating y_{ii} = x_i

Note. If the above statement is correct or fixes the problem exactly, [MIP] can be solved trivially as soon as N_i set.

We consider each i in turn. From N_i select the top N neighboring streets in descending order of weight. This is your current decision. Update the existing solution if the best solution is found when you iterate through i s.