The tag has no wiki summary.

learn more… | top users | synonyms

-2
votes
0answers
8 views

Inventing a new information management system [on hold]

If we can develop a new information management system. Can it be possible that in the system the internet speeds be increased manifold; such as 2g can act as 3g; 3g can act as 4g?
3
votes
0answers
81 views

Maximum local edge connectivity [migrated]

For a simple graph, the local edge connectivity of vertices $x,y$ where $x\neq y$ is $\lambda(x,y)$ and defined as the maximum number of edge disjoint paths from $x$ to $y$. One can find this by a ...
3
votes
1answer
105 views

Complexity of the decision version of determining a min-cut

I was wondering what the complexity of the following problem is: Given: A flow network $N$ with a source $s$, sink $t$ and a number $k$. Question: Is there an $s$-$t$ cut of capacity at most ...
0
votes
1answer
43 views

For a flow network, is it possible to show that there always exists a maximum flow which would assign integer values to all the edges? [closed]

Is it possible to prove that for a flow network, there always exists a maximum flow which assigns an integer value to every edge?
1
vote
3answers
92 views

Can not follow the example for max-flow-min-cut on Wikipedia

This Wikipedia example is very confusing. Its saying the max flow = min cut. But I see the max flow = 9 and the min cut = 7. If not, how does the capacity =min cut here? Which is the max flow min cut ...
2
votes
2answers
153 views

Don't understand this graph definition

I'm studying for my finals in algorithms and reading the part about flow networks. There's a certain section that has me completely stumped and it is as follows: Given a graph $G= \langle V_G, E_G ...
2
votes
1answer
30 views

Determining the minimum vertex cover in a bipartite graph from a maximum flow/matching using the residual network rather than alternating paths

Wikipedia shows how one can determine the minimum vertex cover in a bipartite graph ($G(X \cup Y, E)$) in polytime from a maximum flow using alternating paths. However, I read that the (S,T) cut ...
2
votes
2answers
126 views

What is the difference between maximal flow and maximum flow?

What is the difference between maximal flow and maximum flow. I am reading these terms while working on Ford Fulkerson algorithms and they are quite confusing. I tried on internet, but couldn't get a ...
1
vote
1answer
27 views

Minimum cut versus sparsest cut? [closed]

My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since ...
1
vote
1answer
49 views

maximum bipartite matching

I am working out with the rooks problem. If there are m rooks on an nxn chessboard,i have to give describe a polynomial (in m and n) time algorithm that finds a maximum-sized subset of the rooks such ...
0
votes
0answers
30 views

Picking an optimal initial congestion window size (high bw, high latency and short bursts)?

What is a known strategy to approach a situation where short bursts of data are being sent very often over a high bandwidth, high latency cable? I am aware of cubic but even that does not utilize a ...
5
votes
3answers
183 views

Maximum number of matched vertexes in a one-to-many bipartite graph

I have a variant of bidding problem at hand. There are N bidders(~20) who bid for items from a pool of many items(~10K). Each bidder can bid many items. I want to maximize the number of bidders who ...
0
votes
1answer
42 views

Network Flow with multiple connected subsets

Given a set of buyers, houses, agents with the following constraints: Agents only know a subset of buyers Agents only know a subset of houses Agents can only do some amount of transactions ...
5
votes
1answer
71 views

Why can't you write the 2-paths problem as a max-flow problem?

This is a follow-up question to this. Consider the 2-paths problem: Given a directed graph $D=(V,A)$ and pairs of vertices $(s_1,t_1)$ and $(s_2,t_2)$, are there paths $P_1 = (s_1,\dots, t_1)$ and ...
1
vote
0answers
152 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 ...
1
vote
1answer
80 views

Prove that every maximal flow yields the same minimal cut

Hi I'm trying to prove the following proposition: Given a network $G,s,t,\omega$ where $\omega$ is the capacity, create a minimal cut cut ${S=\left\{ (s,v)\in E_{G_{r\_max}}\right\} }$ where ...
1
vote
0answers
30 views

residual network for a network with lower and upper bounds?

How does one construct the residual network in such a case? The formula is for edge $(u, v)$ is $$rf(u,v) = (c_{\mathrm{upper}}(u,v) - f(u,v)) + (f(v,u) - c_{\mathrm{lower}}(v, u))\,,$$ where ...
0
votes
0answers
56 views

Saturating all augmenting paths with the minimum edge capacity in max flow

To find the maximum flow in a graph, why doesn't it suffice to only saturate all augmenting paths with the minimum edge capacity in that path without considering the back-edges? I mean, what is the ...
5
votes
0answers
145 views

Understanding Dinic's algorithm using dynamic trees

I have here a directed graph that I used to perform Dinic's algorithm to find maximum flow. I need to adjust this graph and this algorithm to work with dynamic trees (i.e. the Sleator-Tarjan ...
1
vote
1answer
106 views

Finding paths from the result of max flow [closed]

Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them. I would like to enumerate all possible sets of paths that comprise the maxflow. That ...
2
votes
2answers
103 views

State machine with knowledge of prior states?

I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well. Below is an example graph ...
2
votes
1answer
75 views

Multicommodity circulation formulation

On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation ...
2
votes
0answers
268 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 ...
0
votes
3answers
238 views

In flow networks, may source/sink have incoming/outgoing edges?

I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ? Flow-networks are always pictures with no ...
2
votes
1answer
323 views

Maximum number of augmenting paths in a network flow

Let's say we a have flow network with $m$ edges and integer capacities. Prove that there exists a sequence of at most $m$ augmenting paths that yield the maximum flow. A good way to start thinking ...
13
votes
2answers
298 views

Are link-cut trees ever used in practice, for max flow computation or other applications?

Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as ...
0
votes
1answer
106 views

Push relabel algorithms in flow networks

In the CLRS book (http://en.wikipedia.org/wiki/Introduction_to_Algorithms) Chapter 26 (Maximum Flow) page 744 (third edition), there is the following equation - $$ \sum_{u \in U}e(u) \;=\; \sum_{u ...
6
votes
4answers
246 views

XOR-like behavior in flow networks

XOR is not the correct name, but I am looking for some kind of exclusive behavior. I am currently solving a set of different (assignment) problems by modeling flow networks and running a ...
3
votes
0answers
956 views

Remove minimum number of vertices to disconnect the graph

Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink. My intuition tells me ...
2
votes
1answer
411 views

2OPT Approximation Algorithm for Multiway Cut Problem

In the multiway cut problem, the input is an undirected graph $G= (V, E)$ and set of terminal nodes $s_1, s_2,\ldots s_k$ are in $V$. The goal is to find a minimum set of edges in $E$ whose removal ...
7
votes
2answers
2k views

Finding negative cycles for cycle-canceling algorithm

I am implementing the cycle-canceling algorithm to find an optimal solution for the min-cost flow problem. By finding and removing negative cost cycles in the residual network, the total cost is ...
-2
votes
1answer
450 views

Dijskstra's algorithm, maximum flow

For directed graph $(G=(V, E),s,t,{Ce})$ in which we want to maximize max flow. All edge capacities are at least one. Define the capacity of an $s \to t$ path to be the smallest capacities of ...
5
votes
0answers
395 views

A variation in Ford-Fulkerson algorithm

Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow. I was thinking that when we augment a ...
10
votes
2answers
3k views

Maximum Independent Set of a Bipartite Graph

I'm trying to find the Maximum Independent Set of a Biparite Graph. I found this in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow": Problem: ...
2
votes
1answer
251 views

Reason for global update steps in the push-relabel algorithm

I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?
8
votes
1answer
301 views

CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof

In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1 which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| ...
5
votes
1answer
320 views

Why is the complexity of negative-cycle-cancelling $O(V²AUW)$?

We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as ...
7
votes
2answers
2k views

Reducing minimum vertex cover in a bipartite graph to maximum flow

Is it possible to show that the minimum vertex cover in a bipartite graph can be reduced to a maximum flow problem? Or to the minimum cut problem (then follow max-flow min-cut theorem, the claim ...
3
votes
2answers
501 views

Finding the maximum bandwidth along a single path in a network

I am trying to search for an algorithm that can tell me which node has the highest download (or upload) capacity given a weighted directed graph, where weights correspond to individual link ...