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

learn more… | top users | synonyms

0
votes
0answers
14 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
28 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
26 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
7 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
36 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
24 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
37 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
21 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 ...
0
votes
3answers
26 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
13 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
35 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
32 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
13 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
28 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
44 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
59 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
24 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
33 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
38 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
28 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
61 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
57 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
50 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
14 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
132 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
39 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
56 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 ...
1
vote
1answer
492 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, ...
1
vote
1answer
83 views

Help with linear algebra network flow (picture)

I've been stuck on this problem for hours. I keep starting and stopping because I'm not exactly sure what I'm doing. The examples the teacher worked in class were much more straight forward. If ...
0
votes
0answers
25 views

Proof of strong connectednes in digraphs by using maximum flow

G= (V,E) is strongly connected digraph if it has a directed path from i to j for every i,j in V. I want to prove that: G is strongly connected <=> every (S,T) cut in G has at least one arc in each ...
1
vote
0answers
29 views

Jackson network, steady state

My question is below: Consider a network of n queues with a Poisson arrival process of parameter t from outside the network, and independent exponentially distributed service times of ...
0
votes
0answers
43 views

Potential values of minimum cost maximum flow 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 ...
0
votes
1answer
39 views

Flow network: Source with in degree and sink with out degree

I have a flow network G with a single source s and a single sink t, but out-degree(t) is not 0 and in-degree(s) is not 0. Does removing all the edges leaving t and/or entering s change the capacity ...
0
votes
0answers
43 views

Minimum u-v cuts

I am working on the following problem: Consider the $G=(V,E)$ and let $w:E \rightarrow \mathbb{R^+}$ be an assignment of nonnegative weights to its edges. Given $u,v \in V$, let f(u,v) be the weight ...
0
votes
1answer
88 views

Spanning Tree - Equivalent Properties

I am working on the following problem: Suppose that $T$ is a spanning tree of a graph $G$, with an edge cost function $c$. Let $T$ have the cycle property if for any edge $e' \not \in T, c(e') \geq ...
1
vote
1answer
37 views

Finding maximum flow of directed network with two inputs

I am given a directed network graph with three fixed verticess where two of these are "inputs" and and one is the "sink". I'm asked to find the maximal flow through the network. How should go about ...
0
votes
0answers
27 views

Network component detection

Suppose I have a (directed) graph with nonnegative edge weights. I would like to separate the graph into what you might call "$\epsilon$-components", that is, a partition $\{ V_i \}$ of the set $V$ of ...
1
vote
1answer
569 views

Proof of König's theorem

Let $G=(V,E)$ be a graph. $H\subseteq V$ is called a vertex cover of $G$ iff $(u,v)\in E\Rightarrow u\in H\vee v\in H$. Now let's assume $G$ is bipartite, i.e. $V=V_1 \cup V_2$ and $E\subseteq ...
-1
votes
1answer
48 views

The Dons Problem: Minimizing the time for complete diffusion of information [duplicate]

A friend of mine asked me this question recently. He might have heard from somewhere else, but that's the extent of my background on this problem. It might have a completely different name, and I ...
2
votes
1answer
69 views

Flow Graphs: Why do you need the symmetry property of a graph?

$$\begin{gather} f(u,v) \le c(u,v) \tag{Capacity constraint} \\ f(u,v) = -f(v,u) \tag{Symmetry} \\ \sum_{\large{v \in V, v \ne s,t}} f(u,v) = 0 \tag{Conservation of flow} \end{gather}$$ When you are ...
0
votes
0answers
51 views

max flow/ min cut

Im trying to work out a flow of size 10 for the commodity network below (using Ford and Fulkerson algorithm). When working out the flow, would this be an acceptable solution: Where 2 + 2 + 2 + 2 ...
1
vote
0answers
148 views

How to show that union and intersection of min cuts in flow chart is also a min cut

The proof of this is everywhere skipped and said to be collorary of Ford-Fulkerson theorem. It's usually something like: Let $A$ and $B$ be low cuts of a flow chart. Then $A \cup B$ and $A \cap B$ ...
1
vote
0answers
36 views

Graph theory: Linking graph characteristics and minimal cut

I'm currently working on a research involving Graph theory. More specifically, I would like to make an analytical or theoretic connection between different characteristics of the graph (e.g. size, ...
0
votes
1answer
185 views

Duality of max-flow and min-cut: when infinite capacity exists

I am wondering if the celebrated duality between max-flow and min-cut actually tolerates infinite valued capacities. Here is a simple example where it seems not: source s, sink t, five other nodes a, ...
1
vote
1answer
46 views

what is a flow in the context of the Ford-Fulkerson algorithm?

I am learning about the Ford Fulkerson algorithm, but having a hard time getting an intuitive feel for what a "flow" is. Is the "flow" the amount that travels between two adjacent nodes on a graph? Or ...
1
vote
1answer
242 views

Determine whether a graph has a unique max flow

Is there a characterization result/some sufficient conditions that ensure that a graph has a unique max flow? Note that it does not say anything about the min-cuts: a path with all edges having ...
0
votes
1answer
76 views

Decomposing flows on a graph as a sum of cycle flows and source flows

I am reading a paper where they say the following is "easy" but I can't seem to see why. Let $G$ be a finite undirected graph on an edge set $V$ and let $E$ be its set of oriented edges (i.e. each ...
1
vote
1answer
67 views

Prove / Disprove: If the Residual Graph $G_f$ Contains no Path from $u$ to $v$ then $e$ Crosses Some Minimum Cut

Let $G = (V,E)$ be a flow network. Let $e = (u,v)$ be an edge in $E$ and let $f$ be a maximum flow in $G$. Prove or Disprove: If the residual graph $G_f$ contains no directed path from $u$ to ...
0
votes
1answer
68 views

Network's flow - a couple of issues

There are three requirements for the path to be a flow - capacity constraints, skew symmetry, and the flow conservation ( http://en.wikipedia.org/wiki/Flow_network ). Ok, but what if the network ...