Maximum weighted independent set – connected component

Given a weighted connected component, what is the weight of of the maximum independent set, and how many different sets have this weight? A Petersen graph GP(5, 2) with zero vertex weights has three maximal subsets by size, 0 maximum set weight but 76 distinct independent sets with this weight.

Advertisements

Maximum weighted independent set – singletons and forest

Gus wants to open franchises of his restaurant, Los Pollos Hermanos, along Central Avenue. There are n possible locations for franchises, where location i is at mile i on Central. Each location i > 1, is thus a distance of 1 mile from the previous one. There are two rules.

1. At each location, there can be at most one restaurant, and the profit of a restaurant at location i is p_i.
2. Any two restaurants must be at least 2 miles apart.