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

learn more… | top users | synonyms

0
votes
1answer
29 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
23 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
23 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
47 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
19 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
17 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
27 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
18 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
29 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
34 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 ...
0
votes
0answers
14 views

How to find all possible minimum cut in a directed graph?

The problem I have asks me to identify each node in the flow graph to be either: nodes that lie on the sink side of every minimum cut. nodes that lie on the source side of every minimum cut. nodes ...
1
vote
2answers
47 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
14 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 ...
3
votes
0answers
57 views

Split a graph on order to solve min cut max flow algorithm in parallel

I'm working with very big graph (millions of nodes) that have this structure: I'd like to solve the maximum flow/minimum cut problem in parallel by splitting the graph into multiple parts in order ...
2
votes
0answers
31 views

traffic flow: red/green light or stop and move?

I live in the burbs and every day twice I drive through a 4-way intersection (E/W - N/S) that is controlled by a red light at which one has to stop from all directions and may pass in the order of ...
1
vote
0answers
17 views

Max flow on undirected graph with constrained edges

I've been trying for a while to develop an algorithm that counts the maximum number of disjoint vertex paths in a graph, but with an addition of "forced paths". Forced paths are here marked with bold ...
0
votes
0answers
24 views

flow conservation s-t flow

Let $G= (V; E)$ be a flow network with capacities $c:E\to \mathbb{R}$, source $s\in V$ and sink $t \in T$. Show that every $s$-$t$ flow satis fies $$\sum_{v\in V} f(s,v) = \sum_{v \in V} f(v,t)$$ I ...
0
votes
0answers
40 views

LP transformation of multi-commodity flow problem

I have the following multi-commodity flow problem that I would like to bring into canonical LP format. \begin{equation*} \begin{aligned} & \underset{d}{\text{minimize}} & &d(x) = ...
0
votes
0answers
25 views

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

Suppose you have a table such as: $\begin{array}{ccc} 11.998 & 9.083 & 2.919 &|& 24\\ 12.983 & 10.872 & 3.145 &|& 27\\ 1.019 & 2.045 & 0.936 &|& 4\\ ...
1
vote
2answers
104 views

Give an algorithm that computes a fair driving schedule for all people in a carpool over $d$ days

Some people agree to carpool, but they want to make sure that any carpool arrangement is fair and doesn't overload any single person with too much driving. Some scheme is required because none ...
0
votes
1answer
36 views

One question about a network optimization problem.

The network model for this problem is as follows: and from the model, we see that it formed a circle and hence without any calculations, the upper and lower bounds for cell Delta/Ph.D. must be ...
0
votes
0answers
27 views

mathematical formulation Minimum Cost Flow

I have a problem of minimum cost flow that can be defined as the following matrix. I want to solve it how a linear program (without using kruskal algorithms, prim etc). How can I formulate it like a ...
0
votes
1answer
32 views

Minimal disjoint chains covering graph vertex set

I'm looking for references on the following problem: Given a graph $G=(V,E)$, what is the minimum number of simple, disjoint paths that span all the vertices in $V$? i.e., let $P$ be the answer to ...
0
votes
1answer
42 views

Strong Triadic Closure and Nodes that Violate/satisfy it

I am very confused about Strong Triadic Closure and knowing what nodes satisfy and violate it. I know 100%,, if it does NOT violate, then it satisfies it. If there r 3 nodes, and Node A is connected ...
0
votes
0answers
13 views

Estimate time it takes the minimum mean cycle cancelling algorithm to converge

This particular algorithm solves the circulation problem, equivalent to the minimum-capacitated flow. My question rather than only from this particular algorithm, but for combinatorial solutions in ...
0
votes
0answers
51 views

k- maximally link disjoint paths and equations

This problem is NP-complete and also discussed to some extent in Graph problems which are NP-Complete on directed graphs but polynomial on undirected graphs from the level of my reading from various ...
0
votes
1answer
43 views

Problem Solving - Project Crashing Time

My working out: (EST,EFT) times for the activities: A: (0,0) B: (0,8) C: (3,3) D: (10,38) E: (10,18) F: (18,18) G: (25,33) H: (58,58) I: (25,33) J: (45,53) K: (118,118) Finish: (133,133) ...
1
vote
0answers
41 views

Maximal flow in flow-networks

I want to do the task (b),(c) and (d)in the picture above. I have done (b) correctly. For (c) I only found one (s-t) augmenting path, namely (s,1),(1,3),(3,2),(2,4),(4,t) and I only can push one ...
0
votes
0answers
28 views

Successive shortest path with infite distances

I have some error in reasoning while trying to understand the successive shortest path algorithm as described in Ahuja, Magnanti, Orlin "Network flows". The algorithm starts with the zero flow and ...
1
vote
3answers
58 views

Equivalence Graphs

On the basis of this definition: Two graphs are equivalent if they have the same set of edges (ex. (A,B),(A,C)) how would you determine equivalence for graphs that are not labelled: ex.
0
votes
0answers
34 views

Inter-neighbor resistance on triangular prism

Given a triangular prism of infinite length along the X direction. A graph is formed with the set of nodes all the points on an edge of the prism with integer values of X, and the with each node ...
1
vote
1answer
39 views

Reduce problem to max flow

I have the following question: Assume each student can borrow at most 10 books from the library, and the library has three copies of each title in its inventory. Each student submits a list of ...
1
vote
1answer
61 views

Maximum Flow - Ford Fulkerson

I tried using the Ford Fulkerson algorithm with the following question: The result I got was 25: I've been told that my solution is not correct. I was not told what the solution was however. ...
0
votes
1answer
38 views

Find $k$ non-disrupting paths from $s$ to $t$

Given the bidirectional graph $G = (V, E)$ where $V$ = set of Vertices, $E$ = set of Edges; given source node $s$ and destination node $t$. Let $A_i$ ($i = 1, 2,\ldots l$) be the subset of vertices ...
0
votes
0answers
18 views

How do you update primal flow and dual slacks with dual network flow?

Heres the problem Heres my attempt The leaving arc is arc(d,b) since it is negative, now arc(d,b) = 0 The entering arc is arc(g,e) since it is lowest primal flow and in opposite direction of ...
0
votes
0answers
34 views

Prove a problem about Networks(in graph theory)

$S$ and $T$ are two subsets of $V(N)$, which is the set of vertices in network N. Let $S^c$ denotes the complement of $S$ and $[S,S^c]$ be the set of arcs starting in $S$ and finishing in $S^c$. If ...
0
votes
1answer
55 views

Some help with understanding Fulkerson algorithm for maximum flow

I'm learning flow networks. I learned Fulkerson algorithm, but there exists one point that is difficult for me. Sorry for image, but I think this is best the way I can explain my problem. This is an ...
0
votes
1answer
109 views

Network simplex method, leaving and entering variables

Could someone give me a hint on this question, which is a past exam question: Under what circumstances will an entering variable in the network simplex method be the same as the leaving variable? ...
2
votes
0answers
59 views

Flow reduction by removing a set of k edges

I am trying to find an algorithm which recieves as input: 1) a Flow network N(G,c,s,t) in which the capacity of an edge is either 0 or 1 (i.e. Exists or not). 2) a positive integer k The output ...
0
votes
1answer
40 views

Need help with minimum cost network flow problems

Consider the tree solution for the following minimum cost network flow problem: The numbers on the tree arcs represent primal flows while numbers on the nontree arcs are dual slacks. (a) Using the ...
1
vote
2answers
44 views

Spanning Tree, Network Modelling

I'm developing some software at the moment for voip communications (broadcast style comms, think ventrilo or teamspeak) between multiple users without a central server (send voice to server, server ...
0
votes
1answer
44 views

How to find a max flow in a flow network

I'm trying too many days to find an answer for this question with no success, so I hope you can help me. Let's say I have the following flow network: ...
0
votes
2answers
63 views

What is the difference between maximal flow and maximum flow?

I have tried a lot on internet, but I am unable to get a good answer on the difference between maximal and maximum flow in case of network flow. Anybody has an idea? with example would be really ...
1
vote
1answer
61 views

Enquiry to network flow

Could anyone advise me on how to find a feasible flow to the following graph so that the edges $(2,5), (4,5), (6,5),(6,7)$ are saturated? This means, I have to formulate the network flow as a linear ...
0
votes
1answer
62 views

Min-Cost-Flow Problem

Given a directed graph $G = (V,E)$ with a cost function $\gamma: E \to \Bbb R_{\geq 0}$ and two vertices $u,v \in V$. How to reduce the problem of finding a directed path from $u$ to $v$ with minimum ...
0
votes
0answers
15 views

transforming matrix data (enviornmental monitoring) into network (graph) structure

I have the following matrix of data from different locations (column 1), different stations (column 2) for different parameters (cols 3-9). The 0 values are missing data. 906 1 10 8 0 0 0 ...
0
votes
2answers
197 views

Real world application of dominating set?

can anyone tell me about the application of vertex coloring problem and algorithm for vertex color problem in graph or networks.
0
votes
1answer
44 views

the source and the sink have a maximum capacity

Consider a variant of max-flow networks in which all vertices different from the source and the sink have a maximum capacity. As we know, Such a network can be transformed into a usual max-flow ...
1
vote
1answer
83 views

Given a max flow on a graph, how do you determine the actual edges that belong to the minimal cut?

After applying an algorithm (like Ford-Fulkerson) that gives you the max flow over a graph $G(V,E)$, how do you determine the actual edges that belong to the minimal cut (recall the Max Flow/ Min Cut ...
3
votes
1answer
1k views

Finding the max flow of an undirected graph with Ford-Fulkerson

Given the following undirected graph, how would I find the max-flow/min-cut? Now, I know that in order to solve this, I need to redraw the graph so that it is directed as shown below. However, ...