6

The directed versions are much harder. A survey by Nutov available on his web page is a good starting point. http://www.openu.ac.il/home/nutov/Survivable-Network.pdf


4

Your problem is NP-hard. Consider a partition problem instance with input $a_1,\ldots,a_n$. We create a complete bipartite graph with $2$ source vertices each with capacity $\frac{1}{2} \sum_{i=1}^n a_i$, and $n$ sink vertices, where the $i$th vertex has capacity $a_i$. Each edge has infinite capacity. It's easy to verify there is a partition with equal ...


4

The model studied in the following work should be a fairly close match with the model that you described (see in particular graph problems "without edge duplication"): Woodruff & Zhang: "When Distributed Computation is Communication Expensive" http://arxiv.org/abs/1304.4636 See also this work for closely related models: Klauck et al.: "Distributed ...


3

The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one the arcs will get flow 0. This gives the bound $m+n$. In the case of $(s,t)$-flows, we may note that during decomposition the nodes $s$ and $t$ becomes balanced ...


2

You could apply the principle of the Configuration Model (Molloy & Reed'95) to bipartite graphs. It allows generating a network possessing any predefined degree distribution. In the original version, you first generate a set of "stubs", where each node is repeated as many times as its targeted degree (i.e. a node whose degree should be 5 will appear as 5 ...


1

My two cents: The worst case of building $G_\top$ is in $\Omega(n^2)$ time and space: assume $\bot$ contains a single node linked to all nodes in $\top$. Maybe you are not looking for a worst case complexity? Then, $O(\sum_{u\in\bot}(d_u)^2)$ time to build $G_\top$ by listing all edges $u,v$ such that $u$ and $v$ are neighbors of the same node in $\bot$. ...


1

No. You're asking about model selection. Larger sample sizes will allow you to choose more complex models. Read up on the keywords overfit/underfit, model selection, Structural Risk Minimization, and in particular this article: https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=705570


1

Not my field of expertise, but I think this is a relaxation in comparison with real-life scenarios. In actual systems, once a connection has been established and a "packet" has been sent (what packet here means depends on the context of the problem being solved), it is possible that an unscheduled interrupt occurs that pauses this communication and allows a ...


Only top voted, non community-wiki answers of a minimum length are eligible