New answers tagged weighted-graphs
0
votes
Optimizing node removal in a graph to achieve minimal edge weights while maintaining a certain total node weight
The problem is NP-complete by reduction from the knapsack problem, so you should not expect any efficient algorithm that works correctly in all possible cases.
A plausible approach to solve this in ...
D.W.♦
- 164k
1
vote
Accepted
Find the number of sink nodes per source node efficiently
Assuming you are asking about a directed graph:
As far as I am aware, I believe there is no solution that is significantly faster from running DFS once for each source (or, running DFS on the reverse ...
D.W.♦
- 164k
Top 50 recent answers are included