Questions tagged [network-flow]

Network flows are used to model concepts like traffic or water pipe systems. The basic idea is to move as many units of flow from source to sink nodes via edges with limited capacity.

309 questions
Filter by
Sorted by
Tagged with
365 views

Why do source and sink have to be distinct in Ford-Fulkerson?

Recently I have been studying the Ford-Fulkerson algorithm for determining max flow. I do not see why it is not allowed to have the source vertex be the same as the sink vertex. From what I have heard,...
982 views

All minimum cuts in flow network

I'm trying to prove that for a flow network, maximum flow f, and each minimum cut S that ...
768 views

How do bridges divide a larger network into smaller broadcast domains?

I am recently brushing up my computer network knowledge, and came across a seemingly peculiar statement: A network bridge divides a network into smaller broadcast domains. As far as I could grasp ...
1k views

Is is possible compute the max flow with max cost through an instance of maxflow-mincost?

I have a flow network with gains. In practical terms, a gain is the opposite of a cost. So, I interested in finding the maximal gain of a network flow, what could be interpreted as finding a maximum ...
44 views

It is necessary to minimize the functional

Consider the town as a grid $N$ x $N$. Thus, there are $(N+1)(N+1)$ of junctions and $2N(N+1)$ two-way roads. Every intersection has a height. It is known that the upper left intersection has a height ...
64 views

Can we create the level graph from sink to source in Dinitz?

One of the steps of the Dinitz algorithm for computing maximal flows is to create a level graph. It is created from source to sink using BFS. Could we create the level graph from sink to source ...
212 views

Set of vertex-disjoint cycles maximizing different colored vertices

Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$. I am looking to find a set of vertex-disjoint cycles that: First maximizes the ...
953 views

Basic questions about network flow calculations

Flow networks are often constructed when one is interested in measuring how resilient a graph is. The idea goes as follows: two vertices are designated as source $(s)$ and sink $(t)$ respectively, to ...
135 views

436 views

Reduce Min-Cut to 0/1 Integer Program

Given an undirected, weighted graph $G=(V,E)$ and two nodes $s,t \in V$ and weight function $w: E \rightarrow \mathbb{N}$. The weight of a (s,t)-cut $(U, U^C)$ is given by:  w(U,U^C) := \sum_{\{i,...
2k views

maximum flow with all or nothing through each edge

Consider a maximum flow problem, where each edge has a small integer capacity. Now, I want a solution that for each edge uses the entire capacity, or no flow through that edge at all. To avoid the ...
666 views

How can we add back edges in Ford - Fulkerson algorithm?

I was going through the Ford-Fulkerson(FF) algorithm. The given graph is directed and there is an edge from A to B with capacity y. Now sending a flow of x units (x < y) from A to B is equivalent ...
147 views

Successive Shortest Paths vs Ford–Fulkerson

Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page ...
739 views

Does a path exist going through each color only once?

I have a directed, colored graph (each node has a color), and I want to find if a path from node A to node B exists such that the path goes through each color at MOST once. I think this problem can ...
2k views

What does the term maximum-bottleneck (s,t)-path in the context of maximum flow optimization?

I was reading the following notes on maximum flow and it said the term "maximum-bottleneck (s-t)-path" but I couldn't find were it precisely defined it, so I am left guessing what it means. I am ...
785 views

Why is it that the flow value can increased along an augmenting path $p$ in a residual network?

I was learning about Max Flow and Residual Graphs and was wondering if there was a formal proof for the statement: the flow value can increased along an augmenting path $p$ in a residual network ...
399 views

Maximum flow, where such paths as source$\to$node$\to$sink must be ignored

How can the maximum flow of a graph be computed when all nodes of the graph are connected to both sink and source nodes (two hypothetical nodes), and the maximum flow method should ignore such paths ...
268 views

A variation of the baseball elimination problem

I suppose you are all familiar with the baseball elimination problem (it is about determining whether some team with particular number of points can finish in the first place, when there are still ...
173 views

Why not use the channel capacity as the sliding window size?

In a sliding window protocol, if we use the maximum possible capacity of the channel as the size of the sliding window, efficiency will be theoretically 100%. What is the logic behind not doing this? ...
62 views

What does this mean $[X]_1^T$?

I found this in information theory paper, P.3883* the authors states the following Most existing theoretic studies of network coding focus on DAGs due to its simpler structure and dure to the fact ...
381 views

Possible paths in pipe network, without loops and with some one-way valves

I'm working on this project for an oil and gas company. One of the main features is a visualization of their pipe network. I'm trying to create a tree of all possible paths. The only limit I have to ...