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

learn more… | top users | synonyms

0
votes
0answers
11 views

Finding a minimum cut for an (s-t) flow: why not just cut the start/end edges?

Most examples I've seen involve cuts snaking through graphs picking off various edges. My question is why not simply do a cut either involved the edges leaving the source or the edges entering the ...
-1
votes
0answers
10 views

N-dimensional cube - flow network

I would really appreciate some help or hints to these problems. Thank you Let graph $Q_n$ be n-dimensional cube, $n\ge1$, whose vertices creates a set $\{0,1\}^n$ and edges connects vertices, which ...
0
votes
1answer
14 views

Max-Flow Min-Cut

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image? (Something like this - image)
1
vote
0answers
31 views

Maximum flow on a directed, acyclic graph

What would be the best algorithm to use for finding max-flow/min-cut on a directed, acyclic graph with integer flows, capacities, and vertex demands? I've been thinking Dinic's Algorithm would be ...
2
votes
0answers
10 views

Weighted Katz Centrality

Given a graph G with n nodes and adjacency matrix A, the Katz Centrality measure, K(G), is given by $K(G)[i] = \sum_{k=1}^{\infty}\sum_{j=1}^{n}\alpha^k(A^k)_{ji}$ s.t. $\alpha$ is an attenuating ...
0
votes
0answers
12 views

Can the time complexity of maximum-flow algorithm using fattest path method be represented by |V| and |E| only?

I've got a problem with "fattest path" heuristic in Max-Flow algorithms. ( http://www.eecs.berkeley.edu/~luca/cs261/lecture10.pdf ) The problem is 'prove or disprove that the time complexity can be ...
0
votes
1answer
14 views

Network flows - formulating the max flow problem as a min cost flow problem

I have been trying to look this up, and I could only find a min cost flow to max flow transformation on the internet. Apparently, this transformation can be done by setting the costs to 0. Another ...
1
vote
1answer
12 views

What are those weighed graphs called?

Let $G = (V, E)$ be a directed graph, and define the weight function $f : V \sqcup E \to \mathbb{R}^+$ as follows: sum of weights of vertices is 1, if a vertex has edges coming out of it, their ...
1
vote
0answers
25 views

Is there an algorithm to find minimum cut in undirected graph separating source and sink

I have an edge-weighted undirected graph and 2 nodes (often called source and sink). I need to find a set of edges of minimum possible weight, which separates these 2 nodes into 2 weak components. I ...
0
votes
0answers
34 views

Increase max-flow by 1 with minimum changes to edges

Suppose we have a directed graph and we have the maximum flow from $s$ to $t$ as $f$. Now we want the graph to have a flow of $f+1$. This requires us to increase the capacity of a certain subset of ...
1
vote
0answers
28 views

How to define backup paths? Flow networks / virtual network embedding / Linear Programming

I'm working in virtual network embedding, where, in short, there is a physical network in which the links and nodes of a virtual network have to be mapped, taking into account some constraints, such ...
0
votes
0answers
11 views

What condition can I impose on a graph to know the properties of certain subsets

I am sorry for the question being a bit open. I ran into this definition while working on a non graph theoretic problem. I am not a graph theorist myself and I have no idea how to look it up. Any ...
1
vote
1answer
24 views

Max-flow/min-cut to determine densest subgraph

I have been trying to understand how a maximum average degree problem can be solved as a maximum flow problem for my optimization class from this article: ...
2
votes
0answers
22 views

Why it is not trivial that $Z_k$-flow gives $k$-flow

In Diestel graph theory book, theorem 6.3.3 (Tutte 1950) states: A multigraph admits a $k$-flow iff it admits a $\mathbb{Z}_k$-flow. I don't understand why do we need a proof, because, by ...
0
votes
0answers
28 views

Identify the four alternative routes which could be critical..

Network diagramm Dependency table
0
votes
1answer
39 views

Is there any algorithm to find all the solutions of the following special linear Diophantine system?

Consider the following system. 1) $a_{11}x_1 + a_{21}x_2 + \cdots + a_{m1}x_m=d_1$ 2) $a_{12}x_1 + a_{22}x_2 + \cdots + a_{m2}x_m=d_2$ $\vdots$ n) $a_{1n}x_1 + a_{2n}x_2 + \cdots + a_{mn}x_m=d_n$ ...
0
votes
0answers
21 views

It would be nice if someone has some idea! (A Diophantine system associated with a network flow)

Assume that we are given a connected network flow with n nodes, $\{1, ..., n\}$, and m arcs. For each arc, say $x_{ij}$ from node i to node j, there is a maximum capacity level given as $M_{ij}$. ...
0
votes
1answer
45 views

Shortest Path Problem as a Minimum Cost Flow Problem

I have to formulate the well known shortest path problem as a min-cost flow problem, but I don't know how to do it. I need your help and suggestions. Thanks in advance!
0
votes
0answers
10 views

What measures of centrality exist for fully connected networks with weighted directed edges?

I have a network of cities with transport links between them. The transport links are not symmetric in both directions, therefore asymmetric edges between nodes. There is a variable number quantifying ...
0
votes
3answers
140 views

Group Theory vs Graph Theory [closed]

I would like to know that, For a given graph can we find an associated finite group? If there are more than one such group, what are the differences and similarities between them? Here ...
3
votes
1answer
33 views

Is it possible to turn a weighted adjacency matrix into an ODE compartment model?

I have an idea for a project that hinges on this idea. Lets say we have an adjacency matrix of a DiGraph where the i,j entry represents an out-going edge from node i to node j and at this position ...
1
vote
1answer
24 views

Max/Min flow of a network

I have a network: How do I figure out the maximum and minimum possible flow through each undefined branch?
1
vote
1answer
34 views

Airline scheduling using minimum network flow

Consider the following table for an airline company:               ...
1
vote
0answers
25 views

Max Flow - Changing the capacity of an edge

Let $G=(V,E)$ be a flow network from $s$ to $t$. I have a maximum flow $f\colon E\to Z$ that was calculated using Ford-Fulkerson. How can I efficiently update $f$ when I need to subtract the ...
1
vote
1answer
34 views

Reduction to a max flow problem from a sudoku like puzzle

Given an $n$ by $n$ grid of which some of the squares are black and some are white. I'm allowed to mark some of these squares and the question is to prove whether a given grid with given black squares ...
0
votes
0answers
34 views

Real world application of independent sets

Independent sets are closely related to dominating sets. What are the real world applications of independent sets? Correspond to the question: Real world application of dominating set?
0
votes
0answers
4 views

Graph Theory: What is the best kind of network centrality to use to determine flows? sources/sinks?

I am working on a medium-sized (80 vertices), cyclic, directed network with commodities being passed around between agents. Its actually stock market data. I would like to determine who of the ...
1
vote
0answers
15 views

Decompose a flow network into several trivial flows

Let $f$ be a flow in (a directed) network $G$. Show that it is possible to express $f$ as a sum of another flow $f_0$ which value is 0, and at most $|E|$ flows, each of which is trivial - i.e. flows ...
0
votes
0answers
35 views

Conditions for a totally unimodular coefficient matrix of a Multi-Commodity-Minimum-Cost-Flow-Problem

I'm considering the following Multi-Commodity-minimum-Cost-Flow-Problem: This leads us to a coefficient matrix $A$ with $N$ donates the incidence matrix of a directed graph and $I$ is the ...
0
votes
0answers
58 views

Formulating shortest path (and tractable graphical model MAP) as submodular minimization

I'm trying to view maximum a posterior inference in discrete graphical model as a submodular minimization. For example, the linear chain model can be solved efficiently by the Baum-Welch algorithm. ...
0
votes
1answer
20 views

Multi-commodity flow problem. What if only one commodity? (Context: column generation)

What problem can arise when the number of commodities is only one when looking at a multi-commodity flow problem? This question was asked by my professor in the context of column generation and ...
3
votes
0answers
127 views

Linear programming and shortest path

Given the linear programming formulation of the shortest path problem: $$ \begin{align*} \min & \sum_{u,v \in A} c_{uv} x_{uv}\\ \text{s.t } & \sum_{v \in V^{+}(s)} x_{sv} - \sum_{v \in ...
0
votes
1answer
46 views

Books on Multi-Commodity Minimum Cost Flow Problems

I'm searching for books on Multi-Commodity Minimum Cost Flow Problems (MCMCF) with theoretical aspects (solvability, optimality conditions, similar statements like in the case of Min Cost Flow,...). ...
0
votes
1answer
53 views

Network flow as a linear/integer programming problem with special conditional constraints

Consider the classic network flow problem where the constraint is that the inflow to a vertex is equal to the sum of its outflows. Consider having a more specific constraint where the flow cannot be ...
0
votes
1answer
48 views

Proving the congestion of a butterfly network.

In MIT's 6.042j course assignment 6. In problem 5, it is required to prove that a butterfly network has congestion of \sqrt{N}. If we have an 8-input butterfly network and let's assume that all of the ...
1
vote
1answer
58 views

Explain how to find a max $(s-t)$ flow in a network

Explain how to find a max $(s-t)$ flow in a network, where some vertices are assigned capacities giving the maximum flow that can pass through those vertices. and Illustrate this method on the ...
0
votes
1answer
22 views

verifying minimum capacity of cut

So I have a cut $(P,P')$ on some network and its capacity is $13$. Now I'm told to assume that the current flow on the network is the max flow, is the cut of minimum capacity? So far all we've ...
0
votes
0answers
17 views

Airport Networking Flow Problem

I've been studying some introductory network optimization, and I noticed an interesting problem about flight networks. Suppose there are four locations $A$, $B$, $C$, and $D$ hold. One can fly from ...
0
votes
0answers
20 views

Show that the feasible flow problem has a feasible solution if and only if for every subset S $\subseteq$ N, b(S) - u[S,S'] $\leq$ 0.

Show that the feasible flow problem, discussed in Application 6.1 below, has a feasible solution if and only if for every subset S $\subseteq$ N, b(S) - u[S,S'] $\leq$ 0. App 6.1: The feasible flow ...
0
votes
1answer
63 views

How many “cuts” does a flow network have?

Assuming a single source, single sink digraph with |V| vertices, including source s and sink t. How many “cuts” does a flow network have?
0
votes
0answers
12 views

Totally uni-modular matrix

I encountered the following matrix and am wondering whether it is totally uni-modular or not: $$\begin{bmatrix} A_{n\times m} & 0_{n\times m}\\ I_{n\times m} & I_{n\times m}\\ ...
0
votes
0answers
29 views

How to find the minimum cut of smallest size in a Graph using Ford Fulkerson

I read the explanation that we have to remove all the saturated edges and then perform BFS to find connected component of s, but this will in my opinion will return the same set of nodes as in the ...
0
votes
0answers
17 views

Deriving/Fitting Origin-Destination Matrix of Directed Graph Flow

Let me preface this by saying that my this area of Mathematics is not my specialty (so pardon me if this is an easy question that I just cannot articulate correctly). I am trying to find a way to ...
3
votes
1answer
113 views

A equivalent condtion for existence of feasible circulation

A circulation in a directed graph $D$ is a function $g:E(D)\rightarrow\mathbb{R}$ satisfying the conservation condition at every vertex. Let $l,u:E(D)\rightarrow \mathbb{R}^{+}_{0}$ be a lower and ...
0
votes
0answers
24 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
33 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
12 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
62 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
28 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? ...
1
vote
2answers
37 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? ...