Attributes  Values 

rdfs:label
 
rdfs:comment
  In computational geometry, a maximum disjoint set (MDS) is a largest set of nonoverlapping geometric shapes selected from a given set of candidate shapes. Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing. Every set of nonoverlapping 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 (MIS) problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects:

foaf:depiction
 
foaf:isPrimaryTopicOf
 
thumbnail
 
dct:subject
 
Wikipage page ID
 
Wikipage revision ID
 
Link from a Wikipage to another Wikipage
 
Link from a Wikipage to an external page
 
sameAs
 
dbp:wikiPageUsesTemplate
 
has abstract
  In computational geometry, a maximum disjoint set (MDS) is a largest set of nonoverlapping geometric shapes selected from a given set of candidate shapes. Finding an MDS is important in applications such as automatic label placement, VLSI circuit design, and cellular frequency division multiplexing. Every set of nonoverlapping 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 (MIS) problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects:
* For the general MIS problem, the best known exact algorithms are exponential. In some geometric intersection graphs, there are subexponential algorithms for finding a MDS.
* The general MIS problem is hard to approximate and doesn't even have a constantfactor approximation. In some geometric intersection graphs, there are polynomialtime approximation schemes (PTAS) for finding a MDS. 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. In the following text, MDS(C) denotes the maximum disjoint set in a set C.

prov:wasDerivedFrom
 
page length (characters) of wiki page
 
is foaf:primaryTopic
of  
is Link from a Wikipage to another Wikipage
of  