For questions about networks that inhibit source and sink nodes and a notion of flow.

learn more… | top users | synonyms

0
votes
0answers
13 views

Problem on costructing flows in a network with multiple sources and sinks

Problem : Formulate and prove a theorem that gives necessary and sufficient conditions so that a network with multiple sources and sinks has a flow that simultaneously meets all prescribed demands ...
0
votes
0answers
12 views

Conversion of network-like matrix

I have given a network in the following form (Example): x1 + x2 - x3 = 0 x3 + x4 - x5 = 0 x5 + x6 - x7 = 0 where = is something like a node, where flow needs to ...
0
votes
0answers
17 views

Graph of Network-Flow Matrices

This matrix is total unimodular 1 1 1 -1 0 0 0 1 1 0 -1 0 0 0 1 0 0 -1 I've read that nearly all ...
0
votes
0answers
14 views

Delay dependency single server

I have a question regarding dependencies between consecutively served customers at a server. Assume I have two customers arriving at the same server with a fixed gap of $Y$. I'm interested in the ...
0
votes
0answers
10 views

Identify arbitrer policy of a network component

I would like to identify the formula of the service rate of a network component ARB based on input and output rates of flows crossing it. For instance, I have several flows which cross several ...
0
votes
0answers
33 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
0
votes
0answers
8 views

Complexity of the Dinic, Malhotra, Kumar and Maheshwari (DMKM) method

I'm asked to prove that the complexity of the DMKM method is $\mathcal{O}(m\cdot n^{\frac23})$ if all capacities in a network are equal to 1. I have no clue where to start, can anyone give me a hint? ...
0
votes
1answer
18 views

What are dynamic networks.

From my understanding, dynamic networks are similar to traditional models except that they function in continuous time and have edges and nodes that evolve over time? Is this a correct understanding? ...
0
votes
1answer
11 views

Why are dynamic networks probabilistic?

I have a only survey level background in network science but am interested in it. I was browsing wikipedia and read this page, (https://en.wikipedia.org/wiki/Dynamic_network_analysis.) In that ...
2
votes
0answers
30 views

Possible Paths in Pipe Network

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
0answers
25 views

Show that splitting an edge in a flow network yields an equivalent network.

Need help with this question from my Intro to Algorithms book: Show that splitting an edge in a flow network yields an equivalent network. More formally, suppose that flow network $G$ contains edge ...
1
vote
2answers
31 views

Transportation: Minimizing Cost

I am trying to solve this problem, but I have had no luck. I have tried to set this up in MS Excel, so I could use Solver to find the solution, but I don't really know how to form this problem. As far ...
0
votes
0answers
24 views

Find convex efficient columns in Matrix

Consider a path-incidence matrix $A$ of a graph, where vertices are e.g. machines, paths are alternative production paths for a given product and entries $a_{ij}$ denote the workcontent for machine ...
0
votes
1answer
60 views

Optimization problem in flight scheduling

I found this question here The question is I wrote the LP problem as this: Let $x_{ij}$ be the maximum no.of flights between city i and city j. Let $a_0$ be the artificial link and $x_0$ be the ...
2
votes
1answer
32 views

optimization network models

This is a question from Wane Winston 's Book. I don't understand how to do this. I tried to do it this way but it doesn't seem to work. Let $C_{ij}$ be the cost of using box of i $ i>=j$ Then ...
1
vote
0answers
20 views

Max-flow-min-cut using LP duality

https://www.cs.oberlin.edu/~asharp/cs365/papers/Approximation-ch12.pdf is a chapter from Vazirani that discusses max cut-min flow using LP duality. The binary min-cut problem is: \begin{align} ...
1
vote
1answer
34 views

Find if there is a matrix that her sum of each column and row representing two vectors

We have two vectors: $(a_1,...,a_n),(b_1,...,b_m)$. We want to know if there is a matrix $M_{nm}$ that all its elements are from $\left\{0,1\right\}$ with this condition: The sum of all the elements ...
1
vote
1answer
66 views

Question about edge disjoint path

I'm studying about edge disjoint path. If there is 3 distinct vertices (u,v,w) in given Graph G = (V,E), Let there is u -> v has k (k>1) edge disjoint paths, and v -> w has k edge disjoint paths, ...
1
vote
1answer
83 views

Matching between $n$ men and $m$ women

There is a group of $n$ men and $m$ women, and there is a symmetric dating between them (between the men and the women). How can we find a match between the men and the women (depending to the ...
2
votes
1answer
71 views

Flow: how does it work?

How does flow work ? I don't understand what they did. For example, why in the edged marked by 3, in the solution it's written 1 ? Morover, a maximum flow is the number a flow or the then longest flow ...
2
votes
0answers
116 views

Jackson's theorem to optimize mean queue length of a traffic model

I am working on traffic signals for a city transport system. I modeled the city transport using a queuing network as shown in the following image Arrival rate of "A" cars from outside is S1 and ...
0
votes
0answers
53 views

Node potentials of minimum cost flow successive shortest path 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
27 views

A cut is minimal iff forward arcs saturated and reverse arcs flowless

Let $G = (V,A)$ be a network with arc capacity function $c$ and let $f$ be a flow on $G$. An arc $(x,y) \in A$ is said to be saturated if $f(x,y) = c(x,y)$ and flowless if $f(x,y) = 0$. In Flows in ...
0
votes
0answers
18 views

How to prove $\operatorname{val}(f) = f^+(X)-f^-(X)$ in flow networks?

In flow networks, for any subset $X$, the $\operatorname{val}(f) = f^+(X) - f^-(X)$. What is this theorem called and how can I prove it? I know that $f^-(\mathrm{sink}) - ...
1
vote
0answers
10 views

graph has no bridge iff a spanning subgraph of the graph is the support of a flow

A $\textit{bridge}$ of a graph $G=(V,E)$ (finite graph and we allow loops and multiple edges) is an edge $e$ whose removal disconnects $G$. Let $\mathcal{O}$ be an orientation of the edges of $G$. ...
1
vote
0answers
40 views

Max flow in flow network

My homework is to proof that if flow network has at least two max flows then it has infinity max flows. I know that I should not write it here since it is homework but I have been trying to solve ...
0
votes
0answers
26 views

Max Flow Min Cut with a Twist Proof

Let G=(V,E) be an undirected graph with positive integer edge costs. Let the set of paths s-t paths be denoted by P. the set of s-t cuts is denoted by C. Prove by construction that: Find the minimum ...
0
votes
0answers
69 views

Proof of correctness of Bidirectional Dijkstra's algorithm.

Problem 4.52 Network flows Ahuja Magnanti & Orlin Bidirectional Dijkstra's algorithm (Helgason, Kennington, and Stewart [1988]). Show that the bidirectional shortest path algorithm described in ...
1
vote
1answer
374 views

Max flow min-cut after a change in edges of capacity 1

I have been asked the following question: Let G be an input graph to the max flow problem. Let (A, B) be a minimum capacity s−t cut in the graph. Suppose we add 1 to the capacity of every edge in the ...
3
votes
1answer
19 views

linear programming and flow network

Here is the problem: I have hard time understanding the problem , what does it mean by "conservation factors" and how to approach the problem using linear programming. For what I understand, if a ...
0
votes
1answer
44 views

Maximum Flow and Change it by Edges Capacity Products

Suppose we have a Directed Graph and each edges has a positive capacity. if C is a positive constant, i say, if we add or subtract C to all edges capacity, the maximum flow, changed, (maybe increase ...
0
votes
0answers
11 views

Estimate Pathways given Transition Counts between Nodes

We know how many entities enter the system through S1. Entities can move between sections in both directions via S1, S2, S3, S4. Can we estimate likely unique paths per entity given counts in each ...
0
votes
0answers
63 views

Multiplying all edge capacities by a positive number doesn't change the minimum cut

Given is a graph defines a flow network. I need to formal proof the following : If we multiply all edge capacities by a positive number $X$, the minimum cut remains unchanged
1
vote
0answers
64 views

What do you call a network flow problem that allows negative flow values?

I'm trying to solve a relaxed network flow problem, where the relaxation discards the bounds constraints on the network flow (as opposed to a pseudoflow, which discards the flow balance constraints). ...
0
votes
0answers
27 views

$k$-core vs $k$-component?

Can someone tell me what the differences between $k$-core and $k$-components are? Base on what I understand: $k$-core: each vertex connects to at least $k$ others in the subset $k$-component: each ...
0
votes
0answers
19 views

a way to compute energy of a flow on transient trees

Let $T$ be a rooted tree that is also a transient electrical network (so effective resistance from root to infinity is finite) but with recurrent rays. (So effective resistance root to infinity along ...
0
votes
0answers
81 views

Physical meaning of some identity in a weighted undirected graph

Let $G$ be an undirected graph with some weights associated with each node. Weights are normalized, sum is 1 and $w_u$ denotes the weight of node $u$. let $V(G) = C \cup \bar C $. ${\it Case }1: $ ...
0
votes
2answers
169 views

Problem in game theory related to traffic networks

I have learnt game theory for a short period of time and I am not familiar with multi-player non-zero sum games. Here is a problem from my book which I am stuck: In this road network below each of ...
0
votes
1answer
43 views

Minimal cuts in network.

Let $(S_1, \overline{S_1} ) , (S_2, \overline{S_2} )$ be minimum cuts in some network. Thesis: The $(S_1 \cap S_2, \overline{S_1 \cap S_2)}$ is minimum cuts in this network. Thesis is true? Why? I ...
0
votes
0answers
51 views

Maximum Flow in a Network

I have a problem here where I needed to find the maximum flow in a linear network with these constraints: I made this visual in Visio to help me visualize the problem and I created this .lp file ...
1
vote
0answers
31 views

What is $F_P$ and $E(P)$?

I'm reading Handbook of Graph Theory: At this section, he speaks about $F_P$ and $E(P)$. It's not really clear what they are. I guess there is enough context for someone to answer me but if ...
1
vote
0answers
68 views

Inequality in inverse Laplacian

I have the following problem, which is motivated by geometric diffusion on a directed graph. Conjecture. Let $A \in [0,1]^{n\times n}$ be strictly substochastic - i.e. $\forall i ~ \sum_j A_{i,j} ...
0
votes
1answer
22 views

Are there two notions of flow?

I'm reading Jungnickel's Graphs, Networks and Algorithms. He defines the flow as a mapping $f:E\to \mathbb{R}_0^+$, which seems to mean the value of the flow of each edge, but in here: When he ...
0
votes
1answer
26 views

Why $f^{+}(v)-f^-(v) =val(f)$ if $v$ is the source?

I'm reading Bondy/Murthy's Graph Theory: He defines $x$ as the source and $y$ as the sink, reading a bit later in the chapter, he presents this definitions: $$ f^{+}(v)-f^-(v) = \left\{ ...
0
votes
1answer
39 views

Is my idea of incoming/outgoing arcs correct?

I'm reading Jungnickel's Graphs, Networks and Algorithms. I've met the following lemma: I know that $e^{-}$ are the incoming vertices and $e^{+}$ are the outgoing vertices. Then I've tried to ...
0
votes
1answer
35 views

Does the maximum cut implies the minimum flow?

Is it possible to reverse the result of the min-cut max-flow theorem and obtain the result that if you have the maximum cut, then you have the minimum flow? I've been thinking about it, but I have no ...
0
votes
1answer
74 views

A small confusion in network flows (conservation constraints).

I'm reading the Handbook of Graph Theory. I guess It says that the sum of the flows going is equal do the sum of flows going back, I'm confused about what is the value of the flow going ...
0
votes
0answers
62 views

What's the meaning of dual concept?

I've read the following on The Handbook of Graph Theory: 11.1.2 Minimum cuts and Duality An important and dual concept related to maximum flows is that of minimum cuts. I know that the value ...
1
vote
2answers
138 views

Proving Konig-Egervary Theorem from Ford-Fulkerson

I've been going over a proof for Konig-Egervary Theorem from Ford Fulkerson, and I just don't see it. In fact, it just seems false. So I'm not sure what I'm missing. Note: the Konig-Egervary Thm says: ...
0
votes
0answers
62 views

Techniques & Algorithms used to solve Shorted Hamilton Path, Hamilton Circuit Questions

I'm interested in knowing different techniques in approaching the following: Shortest Hamilton Path, Hamilton Circuit (when weights have been given for each edge) Hamilton Circuit - Current method ...