This problem concerns independent sets on "rail line" graphs. These undirected graphs have 2n nodes labeled [1, i], [2, i], 1 < i < n. A function w() assigns a weight to each node. There are edges between [1, i] and [2, i] for each i, as well as edges between [1, i] and [1, i + 1] for 1 ≤ i ≤, n - 1 and between [2, i] and [2, i + 1] for 1 ≤ i ≤ n - 1, for a total of 2(n - 1) + n = 3n -2 edges.

Develop recurrences that could be used to efficiently compute MIS (G) when the input G is a rail line graph. You can express MIS(G) in terms of other quantities of your choosing that you can define; and then provide recurrences for these quantities. You do not need to describe an algorithm to compute MIS(G).

Answer rating: 100% (QA)

The recurrence is very easy to find If G is the rail line graph of 2n vertices then let G be the rai... View the full answer