The tag has no usage guidance.

learn more… | top users | synonyms

-1
votes
0answers
17 views

Computer Ethics and Software Implementations: protecting the right to spread the word anonymously *and permanently* [on hold]

It would be interesting how mathematical models of marketing strategies and simulations of their effects on society could be constructed. We all know of how rumors spread in older societies according ...
1
vote
1answer
48 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 ...
0
votes
0answers
32 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 ...
0
votes
1answer
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 ...
3
votes
0answers
11 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 ...
2
votes
2answers
159 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 ...
1
vote
0answers
31 views

How to construct a network flow problem?

I have the optimization problem given below max $\sum_{i=1}^{N}\sum_{j=1}^{M} x_{ij}R_{ij}$ s.t $\quad 1)\quad \sum_{j=1}^{M} x_{ij}=1 \quad \forall i$ $\quad 2)\quad x_{ij} \in {0,1}$ $\quad ...
0
votes
0answers
45 views

How to find maxflow with minimum number of edges?

I am struggling with the flowing problem: You are given a source s and a sink t and a biparted graph G. All vertices {v} from the left half are connected to the source s with given capacity C[v]. ...
5
votes
2answers
99 views

Is this special case of a scheduling problem solvable in linear time?

Alice, a student, has a lot of homework over the next weeks. Each item of homework takes her exactly one day. Each item also has a deadline, and a negative impact on her grades (assume a real number,...
1
vote
1answer
37 views

Residual Graph in Maximum Flow

I am reading about the Maximum Flow Problem Here. I could not understand the initiation behind the Residual Graph. Why we are considering a back edge while calculating the flow. Can anyone help me in ...
3
votes
0answers
29 views

Cheeger constant of a graph versus conductance of a Markov chain

Given some graph $G$ with vertices $V$ and edges $E$, its Cheeger constant $h(G)$ is well defined as $$ h(G) = \min_{S\subset V,0<|S|\leq|V|}\frac{|\partial S|}{|S|}. $$ Given some doubly-...
4
votes
1answer
122 views

Ford-Fulkerson Algorithm not “pushing back” flow

I am told that with every flow network, the Ford-Fulkerson algorithm produces an execution that never decreases the value of the flow on any of the edges (i.e. never “pushes back” the flow on any of ...
3
votes
1answer
129 views

Will the Ford-Fulkerson algorithm always find the max flow if we start from a valid flow?

I stumbled across this question and answer (source): Question: Suppose someone presents you with a solution to a max-flow problem on some network. Give a linear time algorithm to determine ...
0
votes
0answers
9 views

Proving the Multiway cut problem is NP Complete [duplicate]

Problem Statement: Given k nodes: $$ u_1, u_2, u_3..., u_k $$ remove edges of total minimum weight that separates $u_i$ from $u_j$ for all $i != j$ for all k >= 3 I just need some help identifying ...
0
votes
1answer
33 views

How the website owner keep track of your times of access? [closed]

To be specific, I am using the online website of Strait Times News. It limits users to 30 articles to read per month. I just do not understand how do they know you are accessing? We use different IP ...
1
vote
0answers
19 views

Inequalities in a multicommodity min-cut max-flow theorem

I am reading this classic paper by Klein, Plotkin and Rao titled Excluded Minors, Network Decomposition and Multicommodity Flow. In section 3, Theorem 3.1, they define $\hat \ell(vw) = \lceil \ell(vw)...
1
vote
0answers
63 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 ...
1
vote
1answer
133 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 ...
0
votes
1answer
90 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 ...
0
votes
0answers
57 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 ...
-2
votes
1answer
83 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 ...
1
vote
1answer
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? ...
1
vote
1answer
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 ...
1
vote
0answers
99 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 ...
1
vote
1answer
26 views

Flow in a network: Conservation of flow definition

This might be too easy... But I just don't get it. I've been reading about flow in networks and I stumbled upon this definition in wikipedia: https://en.wikipedia.org/wiki/Flow_network $\sum\limits_{...
14
votes
1answer
381 views

Could min cut be easier than network flow?

Thanks to the max-flow min-cut theorem, we know that we can use any algorithm to compute a maximum flow in a network graph to compute a $(s,t)$-min-cut. Therefore, the complexity of computing a ...
-1
votes
1answer
325 views

Prove that Ford-Fulkerson can decide if there is more than one min cuts

Probelm: Deciding whether a network flow graph has more than one min cut. Optimal running time: O(V^2*E). I trying to prove the correctness of the next algorithm: run Dinitz to find max-flow and ...
2
votes
4answers
422 views

Why is this flow a max flow?

According to the Ford-Fulkerson algorithm, I thought that if there was no path from $s$ to $t$, then the flow would be a max flow. In the flow below, there are two paths between $s$ and $t$. Then, how ...
4
votes
1answer
308 views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
2
votes
1answer
49 views

Ford-Fulkerson Running Time

This question might be really basic but every source seems to skip over a couple of steps neither of which seem trivial to me. It would be great if someone could explain them! In the analysis of Ford-...
3
votes
1answer
114 views

Maximum Flow with Binary Capacities

Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow ...
-1
votes
1answer
79 views

Max-Flow Min-Cut Theorem Intuition

What is the intuition behind the Max-Flow Min-Cut Theorem? I know that the Min-Cut is the dual of Max-Flow when formulated as a linear program, but the result seems artificial to me.
1
vote
0answers
45 views

Network clearance algorithms

In the network clearance problem, we are given a simple undirected graph with a capacity assigned to each edge (and/or to each vertex). Each edge can transport up to its capacity each time step (i.e., ...
0
votes
3answers
86 views

Literature on network-flow (optimization) approximation algorithms

I've been searching on literature on approximation algorithms in the context of network-flow problems (optimization) to finish my bachelor degree. However, I have been looking in several well-known ...
3
votes
1answer
244 views

Linear programming formulation of cheapest k-edge path between two nodes

Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges. Here is my attempt using a flow network: \begin{align} \...
2
votes
1answer
144 views

“Minimum” maximum flow with extra capacities

Problem: Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
0
votes
0answers
19 views

Algorithm: “Minimum” maximum flow with extra capacities [duplicate]

Problem: Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow F, ...
1
vote
0answers
124 views

Does Edmonds Karp take back-edges into account?

I amb doubting with the implementation of the Edmonds-Karp implementation of the Ford-Fulkerson algorithm. This is a problem with flow networks. As I understand the algorithm, it consists on taking ...
3
votes
1answer
167 views

Global relabeling heuristic: Push-relabel maxflow

I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues. I have ...
3
votes
1answer
102 views

Unsplittable flow in capacitated networks

I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be ...
1
vote
0answers
22 views

MaxSNP flow problems

Currently, I'm trying to understand the definition and notion of MaxSNP and MaxSNP-hardness. I see that several combinatorical problems such as Max-3SAT are in MaxSNP since one can easily express them ...
1
vote
0answers
173 views

Getting ALL negative weight cycles of a graph using Bellman-Ford

I'm doing a min cost assignation problem to assign doctors to their working days for a hospital. After correctly getting the max flow with Ford-Fulkerson algorithm, I would like to use the cycle ...
-1
votes
1answer
66 views

How to find a minimum cut of a network flow?

I am currently reading the lecture slides from Princeton regarding network flows but I cannot understand how they manage to find out minimum cuts from a directed graph. Could someone explain how ...
12
votes
1answer
361 views

Compute a max-flow from a min-cut

We know that computing a maximum flow resp. a minimum cut of a network with capacities is equivalent; cf. the max-flow min-cut theorem. We have (more or less efficient) algorithms for computing ...
1
vote
1answer
137 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
2
votes
1answer
37 views

Are there FPTASs for the min cost flow problem?

In literature, one can find many approximation algorithms for the multicommodity min cost flow problem or other variants of the standard single-commodity min cost flow problem. But are there FPTASs ...
1
vote
1answer
117 views

Ford-Fulkerson algorithm clarification

In the second edition of the book of Cormen "Introduction to Algorithms" appears the following example (in the left part is the residual network while in the right part shows the flow results): I ...
2
votes
0answers
23 views

Distributed push relabel with changing graph topology

There is at least one (1) distributed version propsosed for the push-relabel maximum-flow algorithm. I wonder if and how this algorithm can cope with nodes leaving or enterig the graph during runtime. ...
-1
votes
1answer
39 views

Determine whether there is a valid rounding in a table of numbers

I was told this question would be better suited here: Suppose you have a table such as: $\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 &|&...
0
votes
0answers
66 views

sum of max flow in residual graph and value of flow

My teacher today explained us this . Consider a network and suppose that at any stage during the application of the Edmonds Karp algorithm to find the max flow, let ...