# Tagged Questions

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

9 views

### Finding the lowest amount of edges in all minimum cuts in flow network

Given a network N, I want to find the minimum cut that has the lowest number of edges in it. I thought about: Find the maximum flow (with Dinitz algorithm for example) Increase the capacity function ...
30 views

13 views

### Network with more than one maximum s-t flow

I'm struggling to think of an example of a network with more than one maximum s-t flow. In addition, is there an efficient way to identify whether or not a network has a unique maximum s-t flow?
29 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 ...
17 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 up ...
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 ...
958 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 ...
24 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 ...
29 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 ...
30 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)
40 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 ...
27 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 ...
17 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 ...
23 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 ...
13 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 ...
44 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 ...
13 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 ...
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: https://hal.archives-ouvertes.fr/inria-...
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 definition,...
52 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$ ...
28 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}$. ...
55 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!
39 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 ...
169 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 ...
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 ...
29 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?
48 views

### Airline scheduling using minimum network flow

Consider the following table for an airline company:                          &...
30 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 ...
45 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 ...
48 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?
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 ...
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 ...
40 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 ...
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. ...
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 ...
132 views

36 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 ...
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 ...