Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+,b∈V×V} to represent costs between every node regardless of whether (u,v) ∈E or not. Now, we want to add some edges M⊂E into the graph G which makes graph G^'=G+M is a 2-connected graph (G^' allow the appearance of multiple edges while graph G is not) such that weights of edge set of M is minimize.

  • $\begingroup$ I don't understand. Connectivity doesn't depend on the weights so just take the unweighted solution and set every weight to 1, assuming the weights are positive integers. If the weights are real, rational or could be negative, then there is no minimum solution, since you can always make the weights smaller. $\endgroup$ – David Richerby Nov 7 '18 at 13:48
  • $\begingroup$ What do you mean by "adding M into the graph G"? Isn't $M$ already in $G$? $\endgroup$ – xskxzr Nov 7 '18 at 14:01
  • $\begingroup$ @DavidRicherby Every edge you could potentially add has an associated cost. $\endgroup$ – Yuval Filmus Nov 7 '18 at 23:06
  • 1
    $\begingroup$ 2-connected graph means removing one node does not disconnect the graph. I don't see why changing an edge to multiple edges make things better. $\endgroup$ – xskxzr Nov 8 '18 at 9:25
  • 1
    $\begingroup$ @binglintao It doesn't seem to be like maximum matching at all. Maximum matching involves finding a set of edges that are already in the graph and have well-defined weights. Your problem involves adding new edges to the graph. Since they don't exist, they don't have weights already defined. So what are these weights? Please give a clear, formal statemnet of the problem, and please do it by editing the question, rather than commenting. $\endgroup$ – David Richerby Nov 8 '18 at 10:47

$2$-connectedness is the same as bridgeless.

So $M$ must be the set of bridges in $G$ no matter how large or small their sum is.

  • $\begingroup$ The set $M$ should consist of edges not already in $G$. $\endgroup$ – Yuval Filmus Nov 8 '18 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.