# Tagged Questions

The tag has no usage guidance.

12 views

### Can max-flow with mutually exclusive edges be reduced to standard max-flow problem?

I'm working with a flow network like the following: The source s has four edges, each with capacity 1, out to the nodes A, B, C, and D. All of A, B, C, and D have edges to two other nodes, X and Y, ...
17 views

### Why Transmission depends on the Interference of other Links

I was reading Congestion aware channel allocation with route scheduling in wireless cognitive radio mesh network, (by Jia et el, Computers and Electrical Engineering 39 (2013) 1346–1357) and I found- ...
14 views

### What's the relationship of max-flow-min-cut and Markov Random Fields?

I am trying to follow this paper [1]. There is a relationship between Markov Random Fields (MRF) to max-flow-min-cut. An MRF can be represented as an undirected graph, and you can find flow through it,...
34 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,...
27 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 ...
55 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 ...
34 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 ...
30 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 ...
13 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 ...
164 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 ...
33 views

64 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 ...
137 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 ...
97 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 ...
59 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 ...
84 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 ...
49 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? ...
49 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 ...
102 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 ...