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

learn more… | top users | synonyms

-1
votes
0answers
7 views

Disjoint paths in a digraph

I have a digraph such as every vertex in it has the same amount of edges coming in and out. So, if for a pair of vertices (x and y) there are k > 0 edge-disjoint paths that go from x to y. Can I ...
0
votes
0answers
23 views

Maximum and Sets of vertex-disjoint paths in a not-directed graph

Let's consider a weighted graph $G = (V,E)$ not directed. In this graph, there are several sinks $S$, which are vertices. Let's consider one vertex $V$ of this graph (which is a source). The problem ...
0
votes
0answers
16 views

Finding maximum flow using Ford-Fulkerson on an undirected graph?

EDIT2: I just realized that you do indeed write 4/0 as the various paths connect up correctly anyway. It's difficult to wrap my head around but it does work itself out in the end. I will leave this ...
0
votes
0answers
7 views

Normalization of the log-Betweenness Centrality

In the paper I'm reading, the author refers to the betweenness centrality of a node with respect to another node, X. They then go on to define the 'node performance' as the normalized value of the ...
0
votes
0answers
3 views

Solving a max-flow variant

I have a multiple-source multiple-sink directed graph. All vertexes have 1 or 2 inbound and 1 or 2 outbound edges, with the exception of the sources (1 outbound and no inbound) and sinks (1 inbound ...
2
votes
0answers
232 views

Belt Balancer problem (Factorio)

So this question is inspired by the following thread: https://forums.factorio.com/viewtopic.php?f=5&t=25008 In it, the poster is examining an $8$-belt balancer (more on that to come) which he ...
0
votes
0answers
21 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 ...
0
votes
0answers
27 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
26 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
36 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
17 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
14 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
21 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 ...
0
votes
0answers
35 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
29 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
27 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
26 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
1answer
46 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
49 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!
2
votes
0answers
31 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
146 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
34 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
27 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
40 views

Airline scheduling using minimum network flow

Consider the following table for an airline company:               ...
1
vote
0answers
28 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
41 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
35 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
8 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
17 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
37 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
21 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
130 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
47 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
54 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
54 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
59 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
24 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
22 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
66 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
14 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
33 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
120 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 ...