# Tagged Questions

26 views

### k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
36 views

### Maximal flow in flow-networks

I want to do the task (b),(c) and (d)in the picture above. I have done (b) correctly. For (c) I only found one (s-t) augmenting path, namely (s,1),(1,3),(3,2),(2,4),(4,t) and I only can push one ...
31 views

### Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
23 views

### Maximum Flow - Ford Fulkerson

I tried using the Ford Fulkerson algorithm with the following question: The result I got was 25: I've been told that my solution is not correct. I was not told what the solution was however. ...
37 views

### Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
24 views

### Prove a problem about Networks(in graph theory)

$S$ and $T$ are two subsets of $V(N)$, which is the set of vertices in network N. Let $S^c$ denotes the complement of $S$ and $[S,S^c]$ be the set of arcs starting in $S$ and finishing in $S^c$. If ...
25 views

### How to find a max flow in a flow network

I'm trying too many days to find an answer for this question with no success, so I hope you can help me. Let's say I have the following flow network: ...
60 views

### What is the difference between maximal flow and maximum flow?

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really ...
50 views

### Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...
115 views

### Real world application of dominating set?

can anyone tell me about the application of vertex coloring problem and algorithm for vertex color problem in graph or networks.
37 views

### the source and the sink have a maximum capacity

Consider a variant of max-flow networks in which all vertices different from the source and the sink have a maximum capacity. As we know, Such a network can be transformed into a usual max-flow ...
52 views

### Given a max flow on a graph, how do you determine the actual edges that belong to the minimal cut?

After applying an algorithm (like Ford-Fulkerson) that gives you the max flow over a graph $G(V,E)$, how do you determine the actual edges that belong to the minimal cut (recall the Max Flow/ Min Cut ...
380 views

### Finding the max flow of an undirected graph with Ford-Fulkerson

Given the following undirected graph, how would I find the max-flow/min-cut? Now, I know that in order to solve this, I need to redraw the graph so that it is directed as shown below. However, ...
25 views

### Proof of strong connectednes in digraphs by using maximum flow

G= (V,E) is strongly connected digraph if it has a directed path from i to j for every i,j in V. I want to prove that: G is strongly connected <=> every (S,T) cut in G has at least one arc in each ...
42 views

### Potential values of minimum cost maximum flow algorithm

I have a simple directed graph $G(V,E)$ that has a source $s$ and sink $t$. Each edge $e$ of $G$ has positive integer capacity $c(e)$ and positive integer cost $a(e)$. I am trying to find the minimum ...
38 views

### Flow network: Source with in degree and sink with out degree

I have a flow network G with a single source s and a single sink t, but out-degree(t) is not 0 and in-degree(s) is not 0. Does removing all the edges leaving t and/or entering s change the capacity ...
42 views

### Minimum u-v cuts

I am working on the following problem: Consider the $G=(V,E)$ and let $w:E \rightarrow \mathbb{R^+}$ be an assignment of nonnegative weights to its edges. Given $u,v \in V$, let f(u,v) be the weight ...
83 views

47 views

### The Dons Problem: Minimizing the time for complete diffusion of information [duplicate]

A friend of mine asked me this question recently. He might have heard from somewhere else, but that's the extent of my background on this problem. It might have a completely different name, and I ...
69 views

### Flow Graphs: Why do you need the symmetry property of a graph?

$$\begin{gather} f(u,v) \le c(u,v) \tag{Capacity constraint} \\ f(u,v) = -f(v,u) \tag{Symmetry} \\ \sum_{\large{v \in V, v \ne s,t}} f(u,v) = 0 \tag{Conservation of flow} \end{gather}$$ When you are ...
50 views

### max flow/ min cut

Im trying to work out a flow of size 10 for the commodity network below (using Ford and Fulkerson algorithm). When working out the flow, would this be an acceptable solution: Where 2 + 2 + 2 + 2 ...
146 views

### How to show that union and intersection of min cuts in flow chart is also a min cut

The proof of this is everywhere skipped and said to be collorary of Ford-Fulkerson theorem. It's usually something like: Let $A$ and $B$ be low cuts of a flow chart. Then $A \cup B$ and $A \cap B$ ...
46 views

### what is a flow in the context of the Ford-Fulkerson algorithm?

I am learning about the Ford Fulkerson algorithm, but having a hard time getting an intuitive feel for what a "flow" is. Is the "flow" the amount that travels between two adjacent nodes on a graph? Or ...
228 views

### Determine whether a graph has a unique max flow

Is there a characterization result/some sufficient conditions that ensure that a graph has a unique max flow? Note that it does not say anything about the min-cuts: a path with all edges having ...
73 views

### Decomposing flows on a graph as a sum of cycle flows and source flows

I am reading a paper where they say the following is "easy" but I can't seem to see why. Let $G$ be a finite undirected graph on an edge set $V$ and let $E$ be its set of oriented edges (i.e. each ...
67 views

### Prove / Disprove: If the Residual Graph $G_f$ Contains no Path from $u$ to $v$ then $e$ Crosses Some Minimum Cut

Let $G = (V,E)$ be a flow network. Let $e = (u,v)$ be an edge in $E$ and let $f$ be a maximum flow in $G$. Prove or Disprove: If the residual graph $G_f$ contains no directed path from $u$ to ...
67 views

### Network's flow - a couple of issues

There are three requirements for the path to be a flow - capacity constraints, skew symmetry, and the flow conservation ( http://en.wikipedia.org/wiki/Flow_network ). Ok, but what if the network ...
69 views

### What would a Tutte Polynomial =0 represent?

So I'm working on proving (via contradiction) that the flow number $\phi(G)$ of a bridgeless graph $G$ is always defined. I'm using the flow polynomial, and I got to a point where I have $0=T(0,1-u)$. ...
84 views

### Which cut does the “minimum cut” refer to?

My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
139 views

### Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?

I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book. Which does "cut" most commonly refer to? p.s. I am aware that "cut" itself can be defined to ...
949 views

### Do “cut set” and “edge cut” mean the same thing?

The definitions I have are: A cut set of a graph $G$ induced by a partition of $G$'s vertices into sets $X$ and $Y$ is the set of all edges with one endpoint in $X$ and another endpoint in ...
184 views

### Using maximum flow algorithm to check existence of a matrix

Using the maximum flow algorithm, I have to determine if there exists a $3\times 3$ matrix $P$ (such that all elements are $\geq 0$). I'm given: The maximum values of the row sums The column sums ...
145 views

### Two-commodity minimum cost flow with antisymmetric costs

I'm looking at a minimum-cost flow problem in directed acyclic graphs. We are given a DAG plus a cost function that maps an edge to a real-valued cost, and a capacity function that maps an edge to a ...
48 views

### Individual components of flow along edges in a graph

I'm wondering if someone can point me towards understanding this problem better. Suppose I have the graph $G = \{V,E\}$ with vertices $v \in V$ and directed edges $e_{i,j} \in E$. Each node has an ...
130 views

358 views

### Construct dual network for conversion of min-cut problem to shortest path problem

I was wondering if there is some typo in the following description from Section 8.4 p263 of Network Flows: Theory, Algorithms, and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. ...