1 Answers
In computational geometry, a maximum disjoint set is a largest set of non-overlapping geometric shapes selected from a given set of candidate shapes.
Every set of non-overlapping shapes is an independent set in the intersection graph of the shapes. Therefore, the MDS problem is a special case of the maximum independent set problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects:
Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing.
The MDS problem can be generalized by assigning a different weight to each shape and searching for a disjoint set with a maximum total weight.
9 views
Answered