# An Entity of Type : owl:Thing, within Data Space : dbpedia.org associated with source document(s)  In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping 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 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 (MIS) problem. Both problems are NP complete, but finding a MDS may be easier than finding a MIS in two respects:

AttributesValues
rdfs:label
• Maximum disjoint set
rdfs:comment
• In computational geometry, a maximum disjoint set (MDS) is a largest set of non-overlapping 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 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 (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 non-overlapping 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 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 (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 sub-exponential algorithms for finding a MDS. * The general MIS problem is hard to approximate and doesn't even have a constant-factor approximation. In some geometric intersection graphs, there are polynomial-time 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
Faceted Search & Find service v1.17_git51 as of Sep 16 2020   OpenLink Virtuoso version 08.03.3319 as of Dec 29 2020, on Linux (x86_64-centos_6-linux-glibc2.12), Single-Server Edition (61 GB total memory)