New answers tagged weighted-graphs
1
Let $G=\left(V, E=\binom{V}{2}\right)$ be your input graph, let $n=|V|$, and call $w(u,v)$ the weight of edge $(u,v) \in E$. Let $x^* = \max_{A, B} \min_{ (u,v) \in A^2 \cup B^2} w(u,v)$ be the value of an optimal solution to your problem (here $A \cup B = V$ and $A \cap B = \emptyset$).
Suppose that you have a guess $x$ on the value of $x^*$ and let $D_x$ ...
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 ...
Top 50 recent answers are included
