New answers tagged weighted-graphs
2
I'm afraid that this idea does not work (and I actually post this question as homework to my students, the reason being that at first glance it looks sound and complete).
Let $G(V, E)$ denote a graph with a cost function $c:e\in E\mapsto Z$, i.e., both positive and negative whole numbers, and no negative cycles. Let us assume there is an edge $e\langle v_i,...
1
This answer shows this problem is NP-hard. Further research is needed to determine whether it belongs to APX or it is APX-hard.
Let $G$ be a complete directed acyclic graph, i.e., you can name the vertices $1,2,\ldots,n$ and there is an edge $(i,j)$ for all $i<j$. Let $D'=D$, and $k$ is equal to half of the sum of the weights of all vertices. Now there ...
2
You can solve this problem in time $O(|V|+|E|)$ by using dynamic programming. Thirst you order nodes in topological order. Let $v_i$ be the $i$-th node in topological order. Let $E_i$ be the set of edges ending in $v_i$.
If $|E_i\setminus D'| = 0$ then:
$$
d[v_i][0] = 0
$$
otherwise:
$$
d[v_i][0] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \not\...
0
What is the significance of negative weight edges in a graph?
Above link answers your query.
One more example:-
If we want to design some architecture then in the whole circuitry there is flow of current. The whole circuitry can be modeled as graph with device components as vertices and the path between them as edges. In these paths the resistance can be ...
0
I can't think of an exact algorithm and don't know if an efficient one exists. But if you're ok with heuristics and approximate solutions you could try the following:
Find an initial solution:
Repeat the following until every vertex is assigned to a cluster:
Pick a vertex u belonging to no cluster and create a new cluster C = {u0}. Grow a minimum weight ...
Top 50 recent answers are included
