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.
10
-
$\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 RicherbyNov 7, 2018 at 13:48
-
$\begingroup$ What do you mean by "adding M into the graph G"? Isn't $M$ already in $G$? $\endgroup$– xskxzrNov 7, 2018 at 14:01
-
$\begingroup$ @DavidRicherby Every edge you could potentially add has an associated cost. $\endgroup$– Yuval FilmusNov 7, 2018 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$– xskxzrNov 8, 2018 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 RicherbyNov 8, 2018 at 10:47
|
Show 5 more comments
1 Answer
$\begingroup$
$\endgroup$
1
$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$ Nov 8, 2018 at 7:22