Given a directed weighted graph, is there an algorithm that does the following:
- Removes as many edges possible.
- Reduces as many weights as possible.
Given the constraint that the net weight of all edges connected to the vertex (sum of incoming edge weights minus sum of outgoing edge weights) remains the same and every edge weight remains non-negative.
Examples:
The graph "A -10-> B -10-> C" could be reduced to "A-10->C" since vertex B has net zero weights (10 incoming and 10 outgoing)
The graph "A -10-> B -3-> A" could be reduced to "A-7->B".
Thanks.