New answers tagged

3

Let $n := |V| = rk$ be the total number of vertices in the graph. Basically, we are looking for a partition of $V$ into $r$ sets each of size $k$. The total cost will be then the sum of the weights of all edges present in the graph induced by each of these sets. Note that the edges having one end in one of these sets and the other endpoint in another set ...


2

The question is at least poorly worded, since it does not specify $k \leq n$ or require a simple cycle. So any positive-value arbitrage cycle can be "pumped" to generate a cycle with unbounded positive value. If we add the requirement that the cycle is simple, then finding the simple cycle with the maximum product of the weights is equivalent to finding the ...


Top 50 recent answers are included