Questions about graphs in which every edge is associated with a weight.
2
votes
0answers
48 views
Effect of increasing the capacity of an edge in a flow network with known max flow
I need your help with an exercise on Ford-Fulkerson.
Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are ...
2
votes
0answers
23 views
Multicommodity shortest path problem on a directed acyclic graph
I have n commodities with each a unique source and sink node. Each source-sink pair is connected in some manner on a directed acyclic graph. All arc weights are non-negative. The goal is to find the ...
4
votes
2answers
471 views
Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$
Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...
6
votes
1answer
224 views
Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights
I ran into the following problem:
Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut.
For general graphs this is NP-hard, since one ...
5
votes
2answers
95 views
An edge that connects more than two nodes in a graph?
Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
6
votes
1answer
597 views
Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
