2

Let $n=|V|$ and $m=|E|$. Intuitively you want the to return the union of the edges in 1) a maximal spanning forest $F$ of the graph induced by the edges of weight $1$, with 2) a maximal spanning forest $F'$ of the graph obtained by identifying the edges of each tree in $F$ into a single vertex (where each edge in $F'$ actually represents an edge of $G$). ...


1

This answers a different question: a cycle is not necessarily simple. You can use the following dynamic programming solution: fun dfs(v, start_v, c_pos, visited_vertices): if c_pos = c.length then // Used all edges if v = start_v then // Returned to the starting vertex visited_vertices is the answer for the problem ...


1

Welcome to CS.SE. I propose to list all paths that correspond to the given weight sequence, and keep only the one which are cycles it needed, which is then easy. A recursive algorithm that appends an edge with weight equal to the first one in the sequence to paths that correspond to the rest of the sequence then makes the job, right? This leads to the ...


1

I don't know whether there is a name for the transform you want but it can be computed in time $\tilde{O}(N)$ where $N$ is the number of entries of the matrix, assuming that the weights are non-negative. Let the dimensions of the input matrices be $n$ and $m$. Call $A$, $W$, and $D$ the matrix with the pixel data, the weights, and the distances in output, ...


1

Let $G = (V,E)$ be the input graph. And, let $G_{M} = (V,E_{M})$ be an MST of this graph. First, note the following properties of the MST and BMST. An MST is always a BMST If all edges in the graph have distinct edge weights, there is always a unique MST. Let $e$ be any edge in $E_{M}$. Let $(S_{e},V \setminus S_{e})$ be the cut obtained after removing $e$...


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